LeetCode Medium Challenge Day 11 | Optimal Partition of String

QUESTION LINK - CLICK

Problem Overview

Given a string s, we need to partition it into the smallest number of substrings such that no character repeats within any substring. For example, for the string "abac", the optimal partitioning is ["ab", "ac"], resulting in 2 substrings.

Solution Approach

The solution involves traversing the string while maintaining a set of characters for the current substring. The set ensures that all characters in the substring are unique. Here’s a step-by-step explanation of the implemented code:

1. Initialization:

? A HashSet<Character> named set is used to store characters of the current substring. This helps in quickly checking if a character has already been added.

? An int variable substringCount is initialized to keep track of the number of substrings created.

2. Iterate Through the String:

? Traverse each character of the string using a for loop.

? For each character, check if it is already present in the set.

3. Handling Duplicates:

? If a character is found in the set, it indicates that a new substring needs to be started. Increment substringCount to reflect the new substring, and clear the set to start fresh.

4. Add Character:

? Add the current character to the set.

5. Final Adjustment:

? After the loop, if the set contains any characters, it indicates that there is an ongoing substring that needs to be counted. Increment substringCount accordingly.

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int partitionString(String s) {
        Set<Character> set = new HashSet<>();
        int substringCount = 0;

        for (int i = 0; i < s.length(); i++) {
            char currentChar = s.charAt(i);

            if (set.contains(currentChar)) {
                // Start a new substring
                substringCount++;
                set.clear();
            }

            set.add(currentChar);
        }

        // Account for the last substring
        if (!set.isEmpty()) {
            substringCount++;
        }

        return substringCount;
    }
}