# Leetcode - Split a String Into the Max Number of Unique Substrings

October 04, 2020

## Problem Statement

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.``````

## Solution

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 + ()
``````

### Code

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)) {
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);
}``````

### Complexity

Its `O(n!)`, factorial of n.

## Similar Posts

### Min Priority Queue Implementation with Heap Data structure

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

### Find if Array contains Duplicate Number - Leet Code Solution

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

### Container with Most Water - Leet Code Solution

Problem Statement Given n non-negative integers a1, a2, …, an , where each…

### Binary Search Tree (BST) Data Structure

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

### Counting Sort Algorithm

Counting sort runs on relatively smaller set of input. Counting sort calculates…

### How to calculate First Common Ancestor of two Nodes in Binary Tree

First try to understand question. Its a binary tree, not a binary search tree…

## Latest Posts

### Jenkins Pipeline with Jenkinsfile - How To Schedule Job on Cron and Not on Code Commit

Introduction In this post we will see following: How to schedule a job on cron…

### How to Git Clone Another Repository from Jenkin Pipeline in Jenkinsfile

Introduction There are some cases, where I need another git repository while…

### How to Fetch Multiple Credentials and Expose them in Environment using Jenkinsfile pipeline

Introduction In this post, we will see how to fetch multiple credentials and…

### Jenkins Pipeline - How to run Automation on Different Environment (Dev/Stage/Prod), with Credentials

Introduction I have an automation script, that I want to run on different…

### Jenkinsfile - How to Create UI Form Text fields, Drop-down and Run for Different Conditions

Introduction I had to write a CICD system for one of our project. I had to…

### Java Log4j Logger - Programmatically Initialize JSON logger with customized keys in json logs

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