Number of Ways to Split a String
Given a string s
with length n
, how many ways can you split it into two substrings s_1
and s_2
such that the number of unique characters in s_1
and s_2
are the same?
Parameter
s
: A string with lengthn
.
Result
The number of ways you can split it into two substrings that satisfy the condition.
Examples
Example 1:
Input: s = "aaa"
Output: 2
Explanation: It can be split in two ways: "a", "aa"
and "aa", "a"
.
Example 2:
Input: s = "bac"
Output: 0
Explanation: There is no way to split this string into two substrings with equal unique elements.
Constraints
0 <= n <= 10^5
Characters in this string may consist of any alphanumeric character. The characters are case sensitive. That is, same letters with different cases count as different characters.
public class Solution
{
public int CountWaysToSplit(string s)
{
int ways = 0;
if (s?.Length > 0)
{
int[] prefixCount = new int[26];
int[] suffixCount = new int[26];
int prefixUnique = 0;
int suffixUnique = 0;
foreach (char c in s)
{
if (suffixCount[c - 'a']++ == 0)
{
suffixUnique++;
}
}
for (int i = 0; i < s.Length - 1; i++)
{
if (prefixCount[s[i] - 'a']++ == 0)
{
prefixUnique++;
}
if (--suffixCount[s[i] - 'a'] == 0)
{
suffixUnique--;
}
if (prefixUnique == suffixUnique)
{
ways++;
}
}
}
return ways;
}
}
PreviousString has same characters at same positionNextCheck whether two Strings are anagram of each other
Last updated