HackerRank‐String Manipulation - a920604a/leetcode GitHub Wiki

int makeAnagram(string a, string b) {
    vector<int> vec1(26,0), vec2(26,0);
    for(char c:a) vec1[c-'a']++;
    for(char c:b) vec2[c-'a']++;
    int count =0;
    for(int i=0;i<26;++i) count+=abs(vec2[i] - vec1[i]);
    return count;
}

int alternatingCharacters(string s) {
    //AAAA
    int n = s.size(), count=0;
    char pre = s[0];
    for(int i=1;i<n;++i){
        if(s[i]==pre){
            count++;
        }
        pre = s[i];
    }
    return count;
}

string isValid(string s) {
    unordered_map<char,int> mp;
    for(char c:s) mp[c]++;
    vector<int> vec;
    for(auto it = mp.begin(); it!=mp.end() ; ++it) vec.push_back(it->second);
    sort(vec.begin(), vec.end());
    
    int med = vec[vec.size()/2];
    cout<<med<<endl;
    // 111122222, NO
    //  22222223 , YES
    int first = 1;
    for(auto it=mp.begin() ; it!=mp.end() ; ++it){
        cout<<it->first<<": "<<it->second<<endl;
        if(it->second == med+1 || it->second == med-1) { // 111122222
            first-=1; 
            if(first<0) return "NO"; // 22222223
        }
        else if(it->second > med+1) return "NO";  
    }
    return "YES";
}

long substrCount(int n, string s) {
    //      a   s   a   s   d
    //a     1   0   1   0   0
    //s         1   0   1   0
    //a             1   0   0
    //s                 1   0
    //d                     1
    
    //      a   b   c   b   a   b   a
    //a     1   0   0   0   0   0   0
    //b         1   0   1   0   0   0
    //c             1   0   0   0   0
    //b                 1   0   1   0
    //a                     1   0   1
    //b                         1   0
    //a                             1
    
    //      a   a   a   a   
    //a     1   1   1   1
    //a         1   1   1
    //a             1   1 
    //a                 1

    long count =n;
    for(long i=0;i<n;++i){
        long diff = -1;
        for(long j=i+1;j<n;++j){
            if(s[i] == s[j]){
                if(diff==-1) count++; // aa..
                else if(j-diff == diff - i){
                    count++;
                    break;
                }
            }
            else{
                if(diff==-1) diff=j;
                else break;
            }
        }
    }
    return count;
}

int commonChild(string s1, string s2) {
    //      s   a   l   l   y
    //
    //h     0   0   0   0   0
    //a         1   1   1   1
    //r         1   1   1   1   
    //r         1   1   1   1
    //y                     2
    int n= s1.size(), m=s2.size();
    vector<vector<int>> dp(n+1, vector<int>(m+1,0));
    for(int i=1;i<n+1;i++){
        for(int j=1;j<m+1;++j){
            if(s1[i-1] == s2[j-1]) dp[i][j] = 1 + dp[i-1][j-1];
            else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[n][m];
}