GeeksForGeeks - POTD | GFG POTD Answer

class Solution{
  public:
    vector<int> matrixDiagonally(vector<vector<int>>&mat)
    {
        vector<int> ans;
        int n = mat.size();
        for(int i = 0; i < n; ++i){
            if(i % 2){
                for(int j = 0; j <= i; ++j) ans.push_back(mat[j][i - j]);
            }else{
                for(int j = i; j >= 0; --j) ans.push_back(mat[j][i - j]);
            }
        }
        for(int i = 1; i < n; ++i){
            if((i % 2) ^ (n % 2)){
                for(int j = n - i - 1; j >= 0; --j) ans.push_back(mat[i + j][n - 1 - j]);
            }else{
                for(int j = 0; j < (n - i); ++j) ans.push_back(mat[i + j][n - 1 - j]);
            }
        }
        return ans;
    }
};

class Solution {
  public:
    vector<vector<long long>> multiply(vector<vector<long long>> &mat1,vector<vector<long long>> &mat2,long long &m){
      vector<vector<long long>> ans(3,vector<long long>(3,0));
      for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            for (int k = 0; k < 3; ++k)
                ans[i][j] = (ans[i][j] + mat1[i][k] * mat2[k][j])%m;
       return ans;
  }
  vector<vector<long long>> power(vector<vector<long long>> &mat,long long n,long long &m){
      vector<vector<long long>> ans(3,vector<long long> (3,0));
      ans[0][0]=ans[1][1]=ans[2][2]=1;
      while(n){
          if(n%2)ans=multiply(ans,mat,m);
          mat=multiply(mat,mat,m);
          n>>=1;
      }
      return ans;
  }
    long long genFibNum(long long a, long long b, long long c, long long n, long long m) {
        
        if(n<=2)return 1;
        vector<vector<long long>> mat={{a,b,c},{1,0,0},{0,0,1}};
        auto ans=power(mat,n-2,m);
        return (ans[0][0]+ans[0][1]+ans[0][2])%m;
    }
};

class Solution{
public: 
 
 int countPairs(vector<vector<int>> &mat1, vector<vector<int>> &mat2, int n, int x)
 {
        int i = 0, j = n * n - 1;
        int ans = 0;
        while (i < n * n && j >= 0) {
            int r1 = i / n, c1 = i % n;
            int r2 = j / n, c2 = j % n;
            int sum = mat1[r1][c1] + mat2[r2][c2];
            if (sum == x) {
                ans++;
                i++;
                j--;
            } else if (sum < x) {
                i++;
            } else {
                j--;
            }
        }
        
     return ans;
 }
};

class Solution {
public:
    string removeDuplicates(string str) {
        unordered_set<char> seen;
        string result = "";

        for (char ch : str) {
            if (seen.find(ch) == seen.end()) {
                seen.insert(ch);
                result += ch;
            }
        }

        return result;
    }
};

class Solution 
{
  public:
    char nthCharacter(string s, int r, int n) 
    {
        while(r--) 
        {
            string temp;
            for(int i = 0; i <= n; i++) 
            {
                if(s[i] == '1')
                    temp += "10";
                else
                    temp += "01";
            }
            
            s = temp;
        }
        
        return s[n];
    }
};

class Solution{
public: 
 bool sameFreq(string s)
 {
     map<char, int> freq;
     for(auto c:s) freq[c]++;
     
     int mini = INT_MAX , maxi = INT_MIN;
     for(auto it:freq) 
     {
         mini = min(it.second , mini);
         maxi = max(it.second, maxi);
     }
     
     if(mini == maxi) return true;
     int cnt = 0;
     for(auto it:freq) if(it.second == maxi) cnt++;
     if(abs(mini-maxi) == 1 && cnt == 1) return true;

     return false;
 }
};

class Solution { 
  public: 
    string longestSubstring(string s, int n) { 
      
        int i = 0; 
    int j = 0; 
    string ans = "-1"; 
    int sz =0; 
    while(i<n && j<n) 
    { 
        string str = s.substr(i,(j-i+1)); 
        if(s.find(str,(j+1)) != string::npos) 
        { 
            if(str.size()>sz) 
            { 
                ans = str; 
                sz=str.size(); 
            } 
            j++; 
        } 
        else i++; 
    } 
    return ans; 
    } 
};

class Solution 
{ 
    public: 
        vector <int> search(string pattern, string text) 
        {  
            int n = text.length(); 
            int m = pattern.length(); 
            vector<int> index_arr; 
             
            for(int i=0; i<n; i++) { 
                 
                string temp = text.substr(i, m); 
                // cout<<"temp: "<<temp<<endl; 
                 
                if(temp == pattern) 
                    index_arr.push_back(i+1); 
            } 
             
            return index_arr; 
        } 
      
};

class Solution{ 
    public: 
         
    // A[]: input array 
    // N: size of array  
    int maxIndexDiff(int a[], int n)  
    {  
           int i = 0; 
        int j = n-1; 
        int maximum = INT_MIN; 
        while(i < n){ 
            if(a[i] > a[j]){ 
                j--; 
            } 
            else{ 
                maximum = max(maximum , (j-i)); 
                j = n-1; 
                i++; 
            } 
        } 
        return maximum; 
    } 
};