Strings - Optimal Partition of String

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.

Input: s = "abacaba"
Output: 4
Explanation: Two possible partitions are ("a","ba","cab","a") and ("ab","a","ca","ba").
So, we can return 4.

Input: s = "ssssss"
Output: 6
Explanation: The only valid partition is ("s","s","s","s","s","s").

Constraints:

1 <= s.length <= 10⁵
s consists of only English lowercase letters.

Solution 1 - Check contiguous unique substring using a HashSet

In this approach, we will use a HashSet to uniqueness of a substring and when a repeated character is found increment the count of unique substrings.

Implementation steps:

Create a HashSet to track unique characters, call it set, and an integer result for the result, initialize this with 1 (see note below, why we are initializing it with 1).
Then, loop through the characters of input string s, check if the set already contains the current character or not, if it contains, that means all the characters added until now will form a unique substring. So, increment the result and clear the set for next subsubstring starting from current character, add then add current character to the set.
Finally return the result.

The reason we are initializing result with 1 is that, let say in the input string has just one character s = 'a', in our logic, it will not find the current character in the set and we will not increment result, to account for this, we either can initialize result with 1, as there is always going to be one character , or we can simply add +1 at the end as well.

import java.util.HashSet; public class OptimalPartitionOfString { static int partitionString(String s) { HashSet<Character> set = new HashSet<>(); int result = 1; for(char c : s.toCharArray()) { if(set.contains(c)) { result++; set.clear(); } set.add(c); } return result; } public static void main(String[] args) { System.out.println(partitionString("abacaba")); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of input string s
Space complexity: O(1), though we are using a HashSet to store the characters, at most it will have 26 characters at any given time.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: