Maximize partitions in a String

JavaView on GFG

Time: O(n)

Space: O(26)

Problem Overview

Split string into maximum partitions where each character appears in only one partition.

Intuition

Split string into maximum partitions where each character appears in only one partition.

Algorithm

1Track last occurrence of each character. Greedily extend current partition to include all characters in it. Cut when all resolved.

Common Pitfalls

• Same as LC 763. Track rightmost boundary for current partition. When i == boundary: partition complete.

Maximize partitions in a String.java

Java

// Approach: Greedy. For each character track last occurrence. Extend current partition to cover all seen chars.
// Time: O(n) Space: O(26)
import java.util.*;

class Solution {
    public int maxPartitions(String s) {
        int n = s.length();
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (!map.containsKey(ch))
                map.put(ch, i);
            else {
                map.remove(ch);
                map.put(ch, i);
            }
        }
        int i = 0;
        int j = 0;
        int maxi = -1;
        int cnt = 0;
        List<Integer> ans = new ArrayList<>();
        while (j < n) {
            char ch = s.charAt(j);
            maxi = Math.max(maxi, map.get(ch));
            if (maxi == j) {
                cnt++;
                // If you want the length of that partitioned string
                ans.add(j - i + 1);
                i = j + 1;
            }
            j++;
        }
        // you can return ans.size() as also your answer.
        return cnt;
    }
}

Was this solution helpful?