Leetcode 1525: Number of Good Ways to Split a String
You are given a string
s. You need to determine the number of valid ways to split s into two non-empty substrings such that the number of distinct letters in the left and right substrings is the same.Problem
Approach
Steps
Complexity
Input: A string `s` consisting of lowercase English letters.
Example: s = 'abacb'
Constraints:
• 1 <= s.length <= 10^5
• s consists of only lowercase English letters.
Output: Return the total number of valid splits where the number of distinct letters in both substrings is equal.
Example: For s = 'abacb', the output is 3.
Constraints:
• The output is the number of valid splits.
Goal: Count the number of valid splits based on distinct letters in both substrings.
Steps:
• Track the distinct letters in the left and right parts of the string.
• For each possible split of the string, compare the distinct letters in the two parts.
• If the distinct letters in both parts are equal, increment the count.
Goal: The string can have up to 10^5 characters, so the solution needs to be efficient.
Steps:
• 1 <= s.length <= 10^5
• s consists of only lowercase English letters.
Assumptions:
• The string is not empty and contains at least one character.
• Input: s = 'abacb'
• Explanation: The valid splits are ('aba', 'cb'). Both have 2 distinct letters.
• Input: s = 'abcd'
• Explanation: The valid split is ('ab', 'cd'), both having 2 distinct letters.
Approach: To solve the problem, track the number of distinct letters in both left and right substrings at each split.
Observations:
• A split is valid if the distinct letters in both parts are the same.
• We can use two counters to track distinct letters on both sides of the split as we iterate through the string.
Steps:
• Create two sets to track the distinct letters in the left and right parts of the string.
• Iterate over the string and for each position, split the string into left and right.
• Check if the number of distinct letters in both parts is the same and count the valid splits.
Empty Inputs:
• No empty strings are allowed, as the string must have at least one character.
Large Inputs:
• The solution needs to efficiently handle large inputs up to 10^5 characters.
Special Values:
• All characters in the string are the same.
Constraints:
• The solution should run in linear time relative to the length of the string.
int numSplits(string s) {
map<char, int> left, right;
int n = s.size();
for(int i = 0; i < n; i++)
right[s[i]]++;
int cnt = 0;
for(int i = 0; i < n; i++) {
left[s[i]]++;
right[s[i]]--;
if(right[s[i]] == 0) right.erase(s[i]);
if(left.size() == right.size()) cnt++;
}
return cnt;
}
1 : Function Declaration
int numSplits(string s) {
This line defines the function `numSplits` which takes a string `s` as input and returns an integer, representing the number of valid splits where the number of unique characters in both parts is the same.
2 : Map Initialization
map<char, int> left, right;
Two maps `left` and `right` are initialized to store the frequency of characters in the left and right parts of the string during the iterations.
3 : Size Calculation
int n = s.size();
This line calculates the size of the string `s` and stores it in variable `n`.
4 : Populate Right Map
for(int i = 0; i < n; i++)
This loop iterates through the string `s`, and in each iteration, it increments the frequency of the character `s[i]` in the `right` map, representing the frequency of characters in the right part.
5 : Increment Right Map
right[s[i]]++;
Increments the count of character `s[i]` in the `right` map.
6 : Counter Initialization
int cnt = 0;
The counter `cnt` is initialized to zero. It will store the number of valid splits where the number of unique characters in both left and right parts is the same.
7 : Iterate for Splits
for(int i = 0; i < n; i++) {
This loop iterates through the string again. In each iteration, it updates the `left` and `right` maps to reflect the changes as characters are moved from the right to the left part of the string.
8 : Increment Left Map
left[s[i]]++;
Increments the frequency of character `s[i]` in the `left` map as the character is considered part of the left substring.
9 : Decrement Right Map
right[s[i]]--;
Decrements the frequency of character `s[i]` in the `right` map as the character is now considered part of the left substring.
10 : Remove Zero Count from Right
if(right[s[i]] == 0) right.erase(s[i]);
If the frequency of character `s[i]` in the `right` map becomes zero, it is removed from the map.
11 : Check for Equal Map Sizes
if(left.size() == right.size()) cnt++;
If the number of unique characters in the left and right parts (i.e., the size of the `left` and `right` maps) is equal, it means this split is valid, and the counter `cnt` is incremented.
12 : Return Result
return cnt;
Returns the final value of `cnt`, which represents the number of valid splits where the number of unique characters in both parts is equal.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The solution processes each character once, thus the time complexity is O(n), where n is the length of the string.
Best Case: O(1)
Worst Case: O(n)
Description: The space complexity is O(n) due to the space required to store the distinct letters for each split.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus