Split ways

这是一个Google的OA题.

给一个string, 问通过切分后, 左边string和右边string的unique的char的个数相同, 这样的切分有几个?

说切分, 其实就是counting问题, 先counting一下unique char的个数, 然后再次counting一遍, 从左往右扫, 做切分.

#include <iostream>  // std::cout
#include <algorithm> // std::lower_bound, std::upper_bound, std::sort
#include <vector>    // std::vector
#include <queue>    // std::priority_queue
#include <float.h>
#include <cstdlib>
#include <bits/stdc++.h> 
using namespace std;

/**
 * *
 * Given a string S, 
 * we can split S into 2 strings: S1 and S2. 
 * Return the number of ways S can be split such that the number of 
 * unique characters between S1 and S2 are the same.
 * **/
int split(string str) {
    unordered_map<char, int> count_right;
    int unique_right = 0, res = 0;
    for(char c : str) {
        if(!count_right[c]) {
            unique_right ++;
        }
        count_right[c]++;
    }
    int unique_left = 0;
    unordered_map<char, int> count_left;
    for(char c : str) {
        if(!count_left[c]) {
            unique_left ++;
        }
        count_left[c] ++;
        count_right[c] --;
        if (count_right[c] == 0)
        {
            unique_right--;
        }
        if (unique_right == unique_left)
        {
            res++;
        }
    }
    
    return res;
}
int main()
{
    string s1 = "aaaa";
    string s2 = "bac";
    string s3 = "ababa";
    cout << split(s1) << endl;
    cout << split(s2) << endl;
    cout << split(s3) << endl;
    return 0;
}