Question

All solutions of Biweekly LeetCode contest 46

Answer 1

I know the O(N*26*26) solution , while traversing the string , at each index  i , iterate from 1 to 26 letters, and check the most recent occurrence of a character whose both forms(uppercase and lowercase) haven't appeared yet. Note down its index 'j' . s[j+1....i] is to be noted. Character with maximum 'j' value will create a  string[j+1...i] , remember its length.Now, some characters in this string will still be faulty , they can be removed by repeating the process 26 more times . 

 

Do that for each character at each index and you are done . 

Code  :

#include<bits/stdc++.h>
typedef long long int ll ; 

class Solution {
public:
    string longestNiceSubstring(string s) 
    {
        int a[30]={0}; //for smaller_case_guys!!
        int b[30]={0};
        int c[30]={0};
        int d[30]={0};
        int n = s.size() ; 
        int god[200][3];
        ll k = 0 ;
        int i = 0 ;
        while(i<n)
        {
            int g = int(s[i]) ; 
            int y ;
            if(g>=97)
            {
                y = g-96 ; 
                a[y]=1;
                c[y]=i; 
            }
            else
            {
                y = g-64 ; 
                b[y]=1;d[y]=i ; 
            }
            int need = -605 ; 
            int j = 1 ;
            
            
            while(j<=26)
            {
                
                if(a[j]==0 && b[j]==1)
                {
                    need = max(need,d[j]) ; 
                }
                else if(b[j]==0 && a[j]==1)
                {
                    need = max(need,c[j]) ; 
                }
                else
                {
                    
                }
                
                
                
                j++;
            }
            
              if(need==-605)
            {
                need = -1 ; 
            }
            
            
            
            int l = 1 ; 
            while(l<=26)
            {
            j=1 ; 
            while(j<=26)
            {
                
                if(a[j]==1 && b[j]==1)
                {
                    //need = max(need,d[j]) ; 
                    
                    if(c[j]>need && d[j]>need)
                    {
                        //RAM_RAM!!!!!!!
                    }
                    else
                    {
                        //RAM_RAM!!!
                         need = max(need,c[j]) ; 
                         need = max(need,d[j]) ; 
                    }
                    
                    
                    
                }
                
                j++;
            }
            
            l++;
            }
            
            
            
            
                if(need!=-605 && need<i)
                {
                    god[k][0]=need+1;
                    god[k][1]=i;
                    k++;
                }
            
            
            i++;
        }
        
        int yep = 0 ; 
        i=0;
        while(i<k)
        {
            
            int diff = abs(god[i][0]-god[i][1]) + 1 ; 
            yep = max(diff,yep);
            i++;
        }
        string pass="";
        if(yep==0)
        {
            return pass ; 
        }
        else
        {
            int rem = n+8 ; 
             i=0;
        while(i<k)
        {
            
            int diff = abs(god[i][0]-god[i][1]) + 1 ; 
            if(diff==yep)
            {
                rem = min(rem,god[i][0]);
            }
            i++;
        }
            
            string finally = s.substr(rem,yep);
            return finally ;  
        }
        
    }
};

 

 

Problem-1  : https://leetcode.com/contest/biweekly-contest-46/problems/longest-nice-substring/

Explanation : Generate all possible substrings of the strings in O(n^2) by using 2 loops . 
For each generated string , check if its a good string or not in O(n) using check function . If the substring is good, note down its length and starting position . Output the substring with largest length of all such good substrings . 

We use a check() function, to check if this substring contains all lowercase as well as uppercase letters . We use two arrays 'a' and 'b' of size 30 for that purpose . 

Code : 

#include<bits/stdc++.h>
typedef long long int ll ; 

ll check(string x)
{
    ll a[30]={0};
    ll b[30]={0};
    ll i = 0 ; 
    while(i<x.size())
    {
        ll g = int(x[i]); 
        if(g>=97)
        {
            ll u = g-96 ; 
            if(a[u]==0)
            {
                a[u]=1;
            }
        }
        else
        {
            ll u = g-64 ; 
            if(b[u]==0)
            {
                b[u]=1;
            }
        }
        
        i++;
    }
    
    ll good = 1 ; 
    i=1;
    while(i<=26)
    {
        if(a[i]!=b[i])
        {
            good = 0 ;
        }
        
        i++;
    }
    
    
    return good ; 
    
    
}

class Solution {
public:
    string longestNiceSubstring(string s) 
    {
        string win="";
        ll maxi = 0 ;
        ll n = s.size() ; 
        ll i=0;
        while(i<n)
        {
            ll j ; 
            j=i ; 
            while(j<n)
            {
                ll length = abs(i-j) + 1 ; 
                string s1 = s.substr(i,length);
                ll good = check(s1);
                if(good==1)
                {
                    if(length>maxi)
                    {
                        maxi = length ; 
                        win = s1 ; 
                    }
                }
                j++;
            }
            
            i++;
        }
        
        return win ; 
        
    }
};

We use s.substr(x,y) function in C++ to make implementation easy ! 

O(n^2) solution is also possible . I leave that upto the reader . 

 

 

Answer 2

Problem Name: Form Array by concatenation of subarray

Thinking approach: at the very first I thought this is a simple two-pointer problem, just maintaining 
start and end window is gonna solve this issue. Next thinking was this can be solved by using Longest 
common substring LOGIC, I did implemented this logic and got WA because there can be completely random 
sets of array between subarray.

My next thinking was do approach this question by Longest common Subarray problem LOGIC, this worked. HOW!?
- I started traversing the array from the beginning searching for the very first region where this 
complete array occurs as a substring. take that end index into account and start searching got next array 
and so on. 

ALGO 

Make a function that is going to give the last index of the very first occurrence of the corresponding 
subarray. and iterate it accordingly. This function is going to return the last index of very first 
occurrence of the main array where this array is found.

if you were unable to find the subarray then return a very large index value. When This very large value 
is returned thich should not exist in array then we need to return false, else we found the solution and 
return true. 

problem : https://leetcode.com/contest/biweekly-contest-46/problems/form-array-by-concatenating-subarrays-of-another-array/
CODE

bool canChoose(vector<vector<int>>& a, vector<int>& b)

{       
        auto solve = [](vector<int> &a, vector<int> &b, int startJ)
        {
            int n = a.size();
            int m = b.size();

            vector<vector<int>> dp(n+100, vector<int>(m+100));
            vector<int> ans;
            for(int i=1 ; i<=n ; i++)
            {
                for(int j=startJ; j<=m ; j++)
                {
                    if(a[i-1] == b[j-1])
                        {
                            dp[i][j] = dp[i-1][j-1]+1;
                            if(dp[i][j] == a.size())
                                return j+1;
                        }
                }
            }
            return m+10;
        };

        int prev = 1;
        int m = b.size();
        for(int i=0 ; i<a.size() ; i++)
        {
            int idx = solve(a[i] , b , prev);
            if(idx > m+1)
                return false;
            prev = idx;
        }
        return true;
    }

Problem Name : Longest Nice subarray
(Bruteforce) I did noticed that constrains are way too low, N^2 should work and done. simply make a 
function to check whether a string is nice or not. run this function for every possible subarray. if this
 function return true for a particular subarray and with length > currAns Len, then update your answer.

Problem : https://leetcode.com/contest/biweekly-contest-46/problems/longest-nice-substring/

CODE

string longestNiceSubstring(string s) {

        auto cmp = [](string s)
        {
            int m[256] = {};
            for(auto i : s)
                m[i]++;

            for(int i=0 ; i<256 ; i++)
                {
                    if(m[i])
                    {
                        if(m[i+32] or m[i-32])
                            continue;
                        return false;
                    }
                }
            return true;
        };

        int n = s.length();
        string ans = "";
        for(int i=0 ; i<n ; i++)
        {
            string t = "";
            for(int j=i ; j<n ; j++)
            {
                t += s[j];
                if(cmp(t) and t.length() > ans.length())
                    ans = t;
            }
        }
        return ans;
    }