Split the given string into minimum number of substrings with unique characters such that the concatenation of all the substrings will result in the given string.
Examples:
- "dddd" --> ["d", "d", "d", "d"] --> answer should be 4.
- "abab" --> ["ab", "ab"] --> answer should be 2.
I tried with backtracking approach, but it got timed out.
My code below
private int res;
public int solution(String s) {
res = Integer.MAX_VALUE;
backTrack(s, "", 0, 0);
return res;
}
private void backTrack(String s, String cur, int ind, int splits) {
if(cur.length() == s.length()) {
res = Math.min(res, splits);
return ;
}
for(int i=ind;i<s.length();i++) {
String str = s.substring(ind, i+1);
if(isSafe(str)) {
backTrack(s, cur + str, i+1, splits+1);
}
}
}
private boolean isSafe(String cur) {
Set<Character> hs = new HashSet<>();
for(int i=0;i<cur.length();i++) {
if(hs.contains(cur.charAt(i)))
return false;
hs.add(cur.charAt(i));
}
return true;
}Any suggestions, pls comment below.
Comments (15)