Index for Coding Problems
Sorting Problems Merge Sort Quick Sort Heap Sort Bubble Sort Selection Sort…
October 04, 2020
Given a string s, return the maximum number of unique substrings that the given string can be split into.
You can split string s into any list of non-empty substrings, where the concatenation of the substrings forms the original string. However, you must split the substrings such that all of them are unique.
A substring is a contiguous sequence of characters within a string.
Example
Input: s = "ababccc"
Output: 5
Explanation: ['a', 'b', 'ab', 'c', 'cc']
Input: s = "aba"
Output: 2
Explanation: ['a', 'ba']
Example 3:
Input: s = "aa"
Output: 1
Explanation: It is impossible to split the string any further.
Problems like these are solved through recursions, where you want to extract a portion of string and repeat the same algorithm on the rest of string.
Lets look at the algorithm:
Lets look at one of example:
input=aba
a + (ba)
a + b + (a)
# a is duplicate, it will only (a, b)
Next iteration
ab + (a)
Next Iteration
aba + ()
Lets look at the code:
private int find(String s, Set<String> set) {
int max = 0;
for (int i=0; i<s.length(); i++) {
String sub = s.substring(0, i+1);
if (!set.contains(sub)) {
set.add(sub);
max = Math.max(max, 1 + find(s.substring(i+1), set));
set.remove(sub);
}
}
return max;
}
public int maxUniqueSplit(String s) {
Set<String> set = new HashSet<>();
return this.find(s, set);
}
Its O(n!)
, factorial of n.
Sorting Problems Merge Sort Quick Sort Heap Sort Bubble Sort Selection Sort…
This is kind of preliminary technique of sorting. And, this is the first…
Big-O notation In simpler terms, its kind of a unit to measure how efficient an…
Problem Statement Given two strings s and t , write a function to determine if t…
Problem The Leetcode file system keeps a log each time some user performs a…
Problem Statement You are given a rows x cols matrix grid. Initially, you are…
Introduction So you have a Django project, and want to run it using docker image…
Introduction It is very important to introduce few process so that your code and…
Introduction In this post, we will see a sample Jenkin Pipeline Groovy script…
Introduction We often require to execute in timed manner, i.e. to specify a max…
Introduction In some of the cases, we need to specify namespace name along with…
Introduction In most of cases, you are not pulling images from docker hub public…