1525. Number of Good Ways to Split a String
Problem Description
In this problem, we are given a string s
. Our task is to determine the number of ways we can split this string into two non-empty substrings s_left
and s_right
such that their concatenation adds back to the original string s
(i.e., s_left + s_right = s
) and the number of unique characters in s_left
is the same as the number of unique characters in s_right
. A split that satisfies these conditions is called a good split. We need to return the total count of such good splits.
Intuition
To arrive at the solution, we can use a two-pointer technique that counts the number of unique characters in the left and right parts of the string incrementally. We can start by counting the distinct letters in the entire string s
and create a set to keep track of the distinct letters we have seen so far as we iterate through the string from left to right.
For each character c
in the string s
, we perform the following steps:
- We add the character
c
to the set of visited (or seen) characters, which represents the left part of the split (s_left
). - We decrement the count of
c
in the total character count, which essentially represents the right part of the split (s_right
). - If the count of
c
after decrementing becomes zero, it means that there are no more occurrences ofc
in the right part (s_right
), and we can removec
from the character count for the right part. - After each character is processed, we check if the size of the visited set (number of unique characters in
s_left
) is the same as the number of characters remaining ins_right
. If they are equal, we have found a good split, and we increment our answer (ans
) by one.
By the end of this process, ans
will hold the total number of good splits that can be made in string s
.
Learn more about Dynamic Programming patterns.
Solution Approach
The implementation of the solution follows these steps:
-
Initialize a
Counter
object from Python'scollections
module for strings
. ThisCounter
object will hold the count of each character in the string, which weāll use to keep track of characters in the right part of the split (s_right
). -
Create an empty set named
vis
to track the distinct characters we have encountered so far, which represents the left part of the split (s_left
). -
Set an answer variable
ans
to zero. This variable will count the number of good splits. -
Iterate through each character
c
in the strings
:- Add the current character
c
to thevis
set, indicating that the character is part of the currents_left
. - Decrement the count of character
c
in theCounter
object, reflecting that one less of the characterc
is left fors_right
. - If the updated count of character
c
in theCounter
becomes zero (meaningc
no longer exists ins_right
), removec
from theCounter
to keep the counts and distinct elements accurate for remainings_right
. - Evaluate if there is a good split by comparing the size of the
vis
set with the number of remaining distinct characters ins_right
as denoted by the size of theCounter
. If they are the same, it means we have an equal number of distinct characters ins_left
ands_right
, and thus, incrementans
by one.
- Add the current character
-
After the for loop completes, return the value of
ans
.
Throughout this process, we are using a set to keep track of the unique characters we've seen which is an efficient way to ensure we only count distinct letters. Utilizing a Counter
allows us to accurately track the frequency of characters as we 'move' characters from right to left by iterating through the string, effectively keeping a live count of what remains on each side of the split. Comparing the lengths of the set and the Counter
keys at each step allows us to check if a good split has been achieved without needing to recount characters each time.
The solution is efficient because it only requires a single pass through the string s
, which makes the time complexity of this approach O(n), where n is the length of the string.
Here is the implementation encapsulated in the class Solution
:
from collections import Counter
class Solution:
def numSplits(self, s: str) -> int:
cnt = Counter(s) # Initial count of all characters in `s`
vis = set() # Set to keep track of unique characters seen in `s_left`
ans = 0 # Counter for number of good splits
# Looping through every character in the string
for c in s:
vis.add(c)
cnt[c] -= 1
if cnt[c] == 0:
cnt.pop(c)
ans += len(vis) == len(cnt)
return ans
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Imagine the string s
is "aacaba"
. We need to calculate the number of good splits for this string.
-
First, we create a counter from the whole string
s
which will give us{'a': 4, 'c': 1, 'b': 1}
showing the counts of each character ins
. -
We then initialize the set
vis
to keep track of the unique characters seen ins_left
(initially empty) and set our answer countans
to 0. -
As we iterate through the string:
-
For the first character
'a'
, we add it tovis
(nowvis
is{'a'}
) and decrement its count incnt
(nowcnt
is{'a': 3, 'c': 1, 'b': 1}
). The lengths ofvis
andcnt
are not equal, soans
remains 0. -
Moving to the second character
'a'
, we add it tovis
(which remains{'a'}
since 'a' is already included) and decrement its count incnt
(nowcnt
is{'a': 2, 'c': 1, 'b': 1}
). The lengths ofvis
andcnt
are still not equal, soans
remains 0. -
Now we come to the third character,
'c'
. We add 'c' tovis
(nowvis
is{'a', 'c'}
) and decrement its count incnt
(nowcnt
is{'a': 2, 'c': 0, 'b': 1}
), and since the count of 'c' has reached 0, we remove 'c' fromcnt
(nowcnt
is{'a': 2, 'b': 1}
). The lengths ofvis
andcnt
are now equal (2 each), so we increment ans to 1. -
Then we process the fourth character
'a'
. After adding 'a' tovis
(which remains{'a', 'c'}
) and decrementing its count incnt
(nowcnt
is{'a': 1, 'b': 1}
), we find that the lengths ofvis
andcnt
are still equal (2 each), so we increment ans to 2. -
The fifth character is
'b'
. We add 'b' tovis
(nowvis
is{'a', 'c', 'b'}
) and decrement its count incnt
(nowcnt
is{'a': 1, 'b': 0}
), and remove 'b' fromcnt
since its count is now 0 (nowcnt
is{'a': 1}
). Lengths ofvis
andcnt
are not equal, so ans remains 2. -
Finally, we process the last character
'a'
. We add 'a' tovis
(which remains{'a', 'c', 'b'}
) and decrement its count incnt
(nowcnt
is{'a': 0}
), and then remove 'a' fromcnt
since its count is 0 (nowcnt
is empty). The lengths ofvis
andcnt
are not equal, so ans remains 2.
-
-
After the loop finishes, since there were two points where the count of unique characters in
s_left
ands_right
were the same, the value ofans
is 2.
Therefore, the total number of good splits for the string "aacaba"
is 2.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def numSplits(self, s: str) -> int:
5 # Count the frequency of each character in the string
6 char_count = Counter(s)
7
8 # Initialize a set to keep track of unique characters visited so far
9 visited_chars = set()
10
11 # Initialize the count for valid splits to 0
12 good_splits = 0
13
14 # Iterate over each character in the string
15 for char in s:
16 # Add the character to the set of visited characters
17 visited_chars.add(char)
18
19 # Decrement the frequency count of the current character
20 char_count[char] -= 1
21
22 # Remove the character from the counter if its frequency becomes 0
23 if char_count[char] == 0:
24 del char_count[char]
25
26 # Increment the count of valid splits if the number of unique characters
27 # in the visited characters and remaining characters are the same
28 good_splits += len(visited_chars) == len(char_count)
29
30 # Return the total number of good splits
31 return good_splits
32
1class Solution {
2 public int numSplits(String s) {
3 // Map to store the frequency of each character in the input string
4 Map<Character, Integer> frequencyMap = new HashMap<>();
5 // Populate the frequency map with the count of each character
6 for (char character : s.toCharArray()) {
7 frequencyMap.merge(character, 1, Integer::sum);
8 }
9
10 // Set to keep track of unique characters encountered so far
11 Set<Character> uniqueCharsSeen = new HashSet<>();
12 // Initialize the count of good splits to 0
13 int goodSplitsCount = 0;
14
15 // Iterate through the characters of the string
16 for (char character : s.toCharArray()) {
17 // Add the current character to the set, indicating it's been seen
18 uniqueCharsSeen.add(character);
19 // Decrease the frequency count of the current character and remove it from the map if the count reaches zero
20 if (frequencyMap.merge(character, -1, Integer::sum) == 0) {
21 frequencyMap.remove(character);
22 }
23
24 // A good split is found when the size of the set (unique characters in the left part)
25 // is equal to the size of the remaining map (unique characters in the right part)
26 if (uniqueCharsSeen.size() == frequencyMap.size()) {
27 goodSplitsCount++;
28 }
29 }
30
31 // Return the total number of good splits found
32 return goodSplitsCount;
33 }
34}
35
1#include <unordered_map>
2#include <unordered_set>
3#include <string>
4
5class Solution {
6public:
7 int numSplits(string s) {
8 // Count the frequency of each character in the string
9 std::unordered_map<char, int> charFrequency;
10 for (char& c : s) {
11 ++charFrequency[c];
12 }
13
14 // This set will store unique characters we've seen so far as we iterate
15 std::unordered_set<char> uniqueCharsSeen;
16
17 int goodSplits = 0; // This will hold the count of good splits
18
19 // Iterate through the string once
20 for (char& c : s) {
21 // Insert the current character into the set of seen characters
22 uniqueCharsSeen.insert(c);
23
24 // If the frequency of the character reaches zero after decrementing, erase it
25 if (--charFrequency[c] == 0) {
26 charFrequency.erase(c);
27 }
28
29 // Increase the count of good splits if the number of unique characters
30 // seen so far is equal to the number of unique characters remaining
31 goodSplits += uniqueCharsSeen.size() == charFrequency.size();
32 }
33
34 // Return the count of good splits
35 return goodSplits;
36 }
37};
38
1// Import relevant classes from TypeScript's collection libraries
2import { HashMap, HashSet } from './collections'; // This line assumes there is a 'collections' module available to import these from
3
4// Function to count the number of good splits in a string
5function numSplits(s: string): number {
6 // Create a frequency map to count the occurrences of each character in the string
7 const charFrequency: HashMap<string, number> = new HashMap();
8 for (const c of s) {
9 charFrequency.set(c, (charFrequency.get(c) || 0) + 1);
10 }
11
12 // This set will store the unique characters we've encountered so far
13 const uniqueCharsSeen: HashSet<string> = new HashSet();
14
15 let goodSplits: number = 0; // Initialize the count of good splits
16
17 // Iterate through the string
18 for (const c of s) {
19 // Add the current character to the set of seen unique characters
20 uniqueCharsSeen.add(c);
21
22 // Decrement the frequency of the character. If it reaches zero, remove it from the map
23 const currentFrequency = charFrequency.get(c) || 0;
24 if (currentFrequency - 1 === 0) {
25 charFrequency.delete(c);
26 } else {
27 charFrequency.set(c, currentFrequency - 1); // Update with the decremented count
28 }
29
30 // Increases the goodSplits counter if the number of unique characters seen is
31 // equal to the number of unique characters that remain in the frequency map
32 if (uniqueCharsSeen.size() === charFrequency.size()) {
33 goodSplits++;
34 }
35 }
36
37 // Return the total number of good splits found in the string
38 return goodSplits;
39}
40
Time and Space Complexity
Time Complexity
The given code snippet involves iterating over each character of the string s
precisely once. Within this single iteration, the operations performed involve adding elements to a set, updating a counter (a dictionary under the hood), checking for equality of lengths, and incrementing an answer counter.
- Adding elements to the
vis
set has an average case time complexity ofO(1)
per operation. - Updating the counts in the
Counter
and checking if a count is zero is alsoO(1)
on average for each character because dictionary operations have an average case time complexity ofO(1)
. - The equality check
len(vis) == len(cnt)
isO(1)
because the lengths can be compared directly without traversing the structures.
Thus, we have an average case time complexity of O(n)
, where n
is the length of the string s
.
Space Complexity
The space complexity is determined by the additional data structures used:
- A
Counter
object to store the frequency of each character ins
. In the worst case, if all characters ins
are unique, the counter would holdn
key-value pairs. - A
set
object to keep track of the characters that we have seen as we iterate. This could also hold up ton
unique characters in the worst case.
Both the Counter
and the set
will have a space complexity of O(n)
in the worst case. Therefore, the overall space complexity is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!