Java - Maximize Partitions in a String

Problem Statement

Given a string S, partition it into the maximum number of substrings such that no character repeats within each substring.

Example 1

Input: S = "abac"

Output: 2

Explanation: The optimal partitions are ["aba", "c"] or ["ab", "ac"].

Example 2

Input: S = "abcbac"

Output: 3

Explanation: The optimal partitions are ["abc", "ba", "c"].

Approach

Use a HashSet to keep track of seen characters in the current partition.

Iterate through the string:

If a character is already in the set, start a new partition.

Reset the set and continue.

Count the number of partitions formed.

Java Code

import java.util.HashSet;

public class MaxPartitions {

    public static int maxPartitions(String s) {

        HashSet<Character> seen = new HashSet<>();

        int partitions = 1; // At least one partition is needed

        for (char c : s.toCharArray()) {

            if (seen.contains(c)) { // If character is already in the current partition

                partitions++; // Start a new partition

                seen.clear(); // Reset the character set

            }

            seen.add(c);

        }

        return partitions;

    }

    public static void main(String[] args) {

        String s = "abcbac";

        System.out.println("Maximum partitions: " + maxPartitions(s)); // Output: 3

    }

}

Complexity Analysis

Time Complexity: O(N) → We traverse the string once.

Space Complexity: O(1) → The HashSet stores at most 26 lowercase letters.

Example Walkthrough

Input: "abcbac"

Steps:

"abc" (Duplicate 'b' found, create partition)

"ba" (Duplicate 'a' found, create partition)

"c" (End of string)

Output: 3

Optimized Approach: Using Bit Masking

Since there are only 26 lowercase letters, we can use a bitmask instead of a HashSet.

public class MaxPartitions {

    public static int maxPartitions(String s) {

        int seen = 0; // Bitmask

        int partitions = 1;

        for (char c : s.toCharArray()) {

            int bit = 1 << (c - 'a'); // Create bitmask for the character

            if ((seen & bit) != 0) { // If character already exists

                partitions++; // Start a new partition

                seen = 0; // Reset bitmask

            }

            seen |= bit; // Add character to bitmask

        }

        return partitions;

    }

    public static void main(String[] args) {

        String s = "abcbac";

        System.out.println("Maximum partitions: " + maxPartitions(s)); // Output: 3

    }

}