Problem Brief

Minimum Number of Non-Empty Disjoint Segments

INTERNOA

See IBM online assessment and hiring insights

Given a string, find the minimum number of non-empty disjoint segments a string can be partitioned into, such that each segment has no repeated characters.

Choose the partitioning that yields the fewest such segments among all possible ways to partition the string.

Note: Each character of the string should be in exactly one segment.

1Example 1

Input

s = "bcoc"

Output

Explanation

Possible partitions of the string: "b", "c", "o", "c" -> 4 "boc", "c" -> 2 "bc", "o", "c" -> 3 It can be concluded that the fewest number of partitioned segments is 2.

2Example 2

Input

s = "abdaa"

Output

Explanation

It can be concluded that the partition "abd", "a", and "a" is the optimal partitioning of s into non-empty disjoint segments, each having no repeating characters.

3Example 3

Input

s = "abcdefghijklmnopqrstuvwxyz"

Output

Explanation

Observed in test results panel: input "abcdefghijklmnopqrstuvwxyz" gives output 1.

Constraints

Limits and guarantees your solution can rely on.

1 ≤ |s| ≤ 2 * 10^5
It is guaranteed that the string s consists only of lowercase English letters.

Draft autosaves locally

public int minimumDisjointSegments(String s) {
  // write your code here
}

Input

"bcoc"

Output