LeetCode — Number of Good Ways to Split a String

Input: s = "aacaba"
Output: 2
Explanation: There are 5 ways to split "aacaba" and 2 of them are good.
("a", "acaba") Left string and right string contains 1 and 3 different letters respectively.
("aa", "caba") Left string and right string contains 1 and 3 different letters respectively.
("aac", "aba") Left string and right string contains 2 and 2 different letters respectively (good split).
("aaca", "ba") Left string and right string contains 2 and 2 different letters respectively (good split).
("aacab", "a") Left string and right string contains 3 and 1 different letters respectively.
Input: s = "abcd"
Output: 1
Explanation: Split the string as follows ("ab", "cd").
Input: s = "aaaaa"
Output: 4
Explanation: All possible splits are good.
Input: s = "acbadbaada"
Output: 2
  • s contains only lowercase English letters.
  • 1 <= s.length <= 10^5
public class Solution {
public int NumSplits(string s) {
Dictionary<char, int> map1 = new Dictionary<char,int>();
Dictionary<char, int> map2 = new Dictionary<char,int>();
foreach(char ch in s.ToCharArray())
if(map1.ContainsKey(ch))
{
int val = map1[ch];
map1[ch] = val + 1;
}
else
{
map1.Add(ch,1);
}
int goodSplit = 0;
for(int i = 0 ; i< s.Length -1 ;++i)
{
if(!map2.ContainsKey(s[i]))
{
map2.Add(s[i],1);

}
else
{
int val = map2[s[i]];
map2[s[i]] = val + 1;
}
int val1 = map1[s[i]];
map1[s[i]] = val1 - 1;
if(val1 == 1)
map1.Remove(s[i]);
if(map1.Count == map2.Count)
goodSplit++;

}
return goodSplit;
}
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store