Optimal Partition of String
Leetcode Daily Challenge (4th April, 2023)
Problem Statement:-
Given a string s, partition the string into one or more substrings such that the characters in each substring are unique. That is, no letter appears in a single substring more than once.
Return the minimum number of substrings in such a partition.
Note that each character should belong to exactly one substring in a partition.
Link: https://leetcode.com/problems/optimal-partition-of-string/description/
Problem Explanation with examples:-
Example 1
Input: s = "abacaba"
Output: 4
Explanation:
Two possible partitions are ("a","ba","cab","a") and ("ab","a","ca","ba").
It can be shown that 4 is the minimum number of substrings needed.
Example 2
Input: s = "ssssss"
Output: 6
Explanation:
The only valid partition is ("s","s","s","s","s","s").
Constraints
1 <= s.length <= 10<sup>5</sup>sconsists of only English lowercase letters.
Intuition:-
As we don't need repeated characters in a partition, we will need something to keep track of the frequency of each character.
We will use a hashmap for that.
We will traverse the string and keep adding the characters to the hashmap if they are not present.
If the character is already present, we will increment the count of the partitions and reset the hashmap to all 0s.
We will return the count of the partitions at the end.
Solution:-
Create a hashmap to keep track of the frequency of each character
Initialize the ans variable to 1 as we will have at least 1 substring.
Traverse the string and check if the character is present in the hashmap or not.
If it is not present, we will add it to the hashmap and put the value as 1.
If it is present, we will increment the count of the partitions and reset all the values in the hashmap to 0. Add the current character to the hashmap and put the value as 1.
Return the ans variable at the end.
Code:-
JAVA Solution
class Solution {
public int partitionString(String s) {
Map<Character, Integer> mp = new HashMap<>();
int ans = 1;
for (char c : s.toCharArray()) {
if (mp.getOrDefault(c, 0) == 0) {
mp.put(c, 1);
} else {
ans += 1;
for (char key : mp.keySet()) {
mp.put(key, 0);
}
mp.put(c, 1);
}
}
return ans;
}
}
Python Solution
class Solution:
def partitionString(self, s: str) -> int:
mp = {}
ans = 1
for i in s:
if mp.get(i,0) == 0:
mp[i] = 1
else:
ans += 1
for j in mp:
mp[j] = 0
mp[i] = 1
return ans
Complexity Analysis:-
TIME:-
The time complexity is O(n) as we are traversing the string only once. In the loop, we also traversed the map which in the worst case can have 26 characters. So, the time complexity in the worst case can be considered as O(26*n) which is O(n).
SPACE:-
The space complexity is O(k), where k is the size of the character set of the input string s. In the worst case, if all the characters in s are unique, then the map mp will have k entries. Therefore, the space required is proportional to the size of the character set.