### Remove nth Node from Last - Leet Code Solution

Problem Statement Given a linked list, remove the n-th node from the end of list…

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:

- For checking unique substrings, you need to take a HashSet
- We would take a substring, check it if its unique.
- If its unique, we will move forward with rest of string in the same 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.

Problem Statement Given a linked list, remove the n-th node from the end of list…

A Binary Search tree (BST) is a data structure which has two children nodes…

Problem Statement Roman numerals are represented by seven different symbols: I…

Here are some tips while giving your coding interviews. 1. Never try to jump to…

Problem Statement Given an array of integers, find if the array contains any…

Problem Statement Given two arrays, write a function to compute their…

Introduction Java log4j has many ways to initialize and append the desired…

Introduction You have a running kubernetes setup, and have a webservice (exposed…

Introduction I have my main website, which I run on Lets say: . Now, there is my…

Understanding Simple Message Workflow First, lets understand a simple workflow…

Exponential Backoff in Rabbitmq Please make sure to read first, why we need the…

Introduction This post has the complete code to send email through smtp server…