

Interview preparation kit, String Manipulation

Sherlok and Valid Srings

• Thought: Run through the following steps

  • (1) Collecting the statistic data of occurance of all the characters in the given string
  • (2) Iterate through the map in (1), and count the occurance of occurance
  • (3) In (1), (2) such as aaabbccc is a : 3, b : 2, c : 3, and the occurance of occurance is 3 : 2 and 2 : 1
  • (4) Considering the situations
    • (4-1) If there are > 2 kinds of occurances, such as aaabbccc, than we must at least 1 a and 1 c, which is not satisfiable
    • (4-2) If only one kind of occurances, such as abcdefg, than already satisfiable
    • The following has only 2 kinds of occurances.
    • (4-3) If the occurance of lower frequency alphabet is only one, then we just easily remove that, such as aaab a^100b, removing one b satisfies the criterium.
    • (4-4) If the higher frequency lower one is only 1 and that occurance of higher frequency is exactly 1, such as bbbcc, removing one b satisfies the criterium. But aaabbbcc is 3 : 2, 2 : 1, should at least remove one a and b, does not satisfies the criterium.
    • (4-5) No matter the occurance of occurance, if higher frequency - lower frequency exceeds 1, then it fails, such as bbbbbbcc (bbbbbbc has been filtered in 4-3)
    • (4-6) The rest failed

• Analysis:

  • Time complexity: O(N), iterating the whole string and implement the statistical data
  • Space complexity: O(N), by using a map data to store the statistical data.

string isValid(string s) 
{
    // step (1)
    unordered_map<char, int> map_1; // stat data for character occurance
    string res;
    int n = s.size();

    for(int i = 0; i < n; i++)
    {
        map_1[s[i]]++;
    }

    // step (2), (3)

    map<int, int> freq_cnt; // order matters
    for(unordered_map<char, int>::iterator it = map_1.begin() ;it != map_1.end(); it++)
    {
        freq_cnt[it -> second]++;
    }
    if(freq_cnt.size() > 2) // step 4-1
    {
        return "NO";
    } 
    else if(freq_cnt.size() == 1) // all the same frequency, ex aabbccddee, we only have 2 : 5 // step 4-2
    {
        return "YES";
    }

    map<int, int>::iterator it = freq_cnt.begin();
    int f1 = it -> first;
    int lower_freq_cnt = it -> second; 

    map<int, int>::iterator it2 = ++it;
    int f2 = it2 -> first;
    int higher_freq_cnt = it2 -> second;

    int lower_freq = min(f1, f2), higher_freq = max(f1, f2);

    if(lower_freq == 1 && lower_freq_cnt == 1) // step 4-3
    {
        return "YES";
    }
    else if(higher_freq - lower_freq == 1 && higher_freq_cnt == 1) // step 4-4
    {
        return "YES";
    }
    else if(higher_freq - lower_freq > 1) // step 4-5 
    {
        return "NO";
    }

    return "NO"; // step 4-6
}