GeeksForGeeks - POTD | GFG POTD Answer

class Solution {
  public:
    vector<int> spirallyTraverse(vector<vector<int> > &matrix) {
        int n = matrix.size(), m = matrix[0].size();
        int dxy[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
        bool vis[n+1][m+1]; memset(vis,false,sizeof(vis));
        vector<int> res;
        int i = 0, j = 0, k = 0;
        while ( true ){
            res.push_back(matrix[i][j]); vis[i][j] = true;
            if ( res.size() == n*m ) break;
            int ni = i + dxy[k%4][0], nj = j + dxy[k%4][1];
            if ( !(ni >= 0 && ni < n && nj >= 0 && nj < m && !vis[ni][nj]) ) k++;
            i += dxy[k%4][0]; j += dxy[k%4][1];
        } return res;
    }
};

class Solution {
public:
    string longestCommonPrefix(vector<string>& arr) {
        if (arr.empty()) return "-1";
        
        string prefix = arr[0];
        for (int i = 1; i < arr.size(); i++) {
            while (arr[i].find(prefix) != 0) {
                prefix = prefix.substr(0, prefix.length() - 1);
                if (prefix.empty()) return "-1";
            }
        }
        
        return prefix.empty() ? "-1" : prefix;
    }
};

class Solution {
  public:
    vector<vector<int>> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    map<pair<int, int>, char> mp;

    void dfs(vector<vector<int>>& mat, int i, int j, vector<vector<int>>& vis, vector<string>& res, string path) {
        int n = mat.size();
        if (i == n - 1 && j == n - 1) {
            res.push_back(path);
            return;
        }
        vis[i][j] = 1;
        for (auto dir : dirs) {
            int x = dir[0] + i;
            int y = dir[1] + j;

            if (x < 0 || y < 0 || x >= n || y >= n || vis[x][y] || mat[x][y] == 0)
                continue;

            dfs(mat, x, y, vis, res, path + mp[{dir[0], dir[1]}]);
        }
        vis[i][j] = 0;
    }

    vector<string> findPath(vector<vector<int>>& mat) {
        mp[{0, 1}] = 'R';
        mp[{1, 0}] = 'D';
        mp[{-1, 0}] = 'U';
        mp[{0, -1}] = 'L';

        int n = mat.size();
        vector<string> res;
        vector<vector<int>> vis(n, vector<int>(n, 0));
        if (mat[0][0] == 1) {
            dfs(mat, 0, 0, vis, res, "");
        }
        sort(res.begin(), res.end());
        return res;
    }
};

class Solution {
  public:
    int rowWithMax1s(vector<vector<int> > &arr) {
        int maxi=0,ind=-1;
        for(int i=0;i<arr.size();i++)
        {
            int c=0;
            int j=arr[i].size()-1;
            while(arr[i][j]!=0){
                c++;
                j--;
            }
            if(maxi<c){
                maxi=c;
                ind=i;
            }
        }
        return ind;
    }
};

class Solution {
  public:

    string removeDups(string str) {
        
        
        vector<int>v(26,0);
        
        for(int i=0; i<str.size();i++){
            v[str[i]-'a']+=1;
        }
        
        string ans="";
        for(int i=0; i<str.size();i++){
            if(v[str[i]-'a']>0){
                ans+=str[i];
                v[str[i]-'a']=0;
            }
        }
        return ans;
    }
};

class Solution{
  public:
  
    int lps(string s1 , string s2 , int i , int j , vector<vector<int>> &dp){
        
        if(i >= s1.length() || j >= s2.length()){
            return 0;
        }
        
        if(dp[i][j] != -1){
            return dp[i][j];
        }
        
        if(s1[i] == s2[j]){
            return dp[i][j] = 1 + lps(s1,s2,i+1,j+1,dp);
        }
        
        int a1 = lps(s1,s2,i+1,j,dp);
        int a2 = lps(s1,s2,i,j+1,dp);
        return dp[i][j] = max(a1,a2);
        
    }
  
    int countMin(string str){
    
        int n = str.length();
        string s1 = str;
        reverse(str.begin(),str.end());
        vector<vector<int>> dp(n+1,vector<int>(n+1,-1));
        return n - lps(s1,str,0,0,dp);
    }
};

class Solution {
  public:

    bool kPangram(string str, int k) {
        unordered_map<char,int> m;
        int extra=0;
        
        // calculate the characters present in excess
        for(int i=0;i<str.size();i++)
        {
            if(!isalpha(str[i]))
            {
                continue;
            }
            if(m[str[i]]==1)
            {
                extra++;
            }
            else{
                m[str[i]]=1;
            }
        }
        
        // calculate the total characters brought in 
        int t=0;
        for(char ch='a';ch<='z';ch++)
        {
            if(extra==0)
            {
                break;
            }
            
            if(m[ch]==0 && extra>0)
            {
                m[ch]=1;
                extra--;
                t++;
            }
        }
        
        // check if all the conditions satisfied
        for(char cc='a';cc<='z';cc++)
        {
            if(m[cc]==0)
            {
                return false;
            }
        }
        if(t<=k)
        {
            return true;
        }
        return false;
        
    }
};