Split ways
这是一个Google的OA题.
给一个string, 问通过切分后, 左边string和右边string的unique的char的个数相同, 这样的切分有几个?
说切分, 其实就是counting问题, 先counting一下unique char的个数, 然后再次counting一遍, 从左往右扫, 做切分.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#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; } |