### Reverse digits of a signed integer - Leet Code Solution

Problem Statement Given a signed integer, reverse digits of an integer. Return…

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 signed integer, reverse digits of an integer. Return…

It is one of a simple algorithm to study for a beginner to understanding sorting…

Max Priority Queue is a data structure which manage a list of keys(values). And…

Here are some tips while preparing for your coding interviews. 1. Do study or…

Big-O notation In simpler terms, its kind of a unit to measure how efficient an…

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

Problem Statement You are given a string text of words that are placed among…

Problem Statement You are given a rows x cols matrix grid. Initially, you are…

Problem The Leetcode file system keeps a log each time some user performs a…

Problem Statement Replace all spaces in a string with ‘%20’ (three characters…

Problem Implement an algorithm to determine if a string has all the characters…

Problem Statement Given a string, determine if it is a palindrome, considering…