Maximize the Number of Partitions After Operations

Maximize the Number of Partitions After Operations - Problem

You are given a string s and an integer k. First, you are allowed to change at most one character in s to another lowercase English letter. After that, you need to perform the following partitioning operation until s is empty:

Choose the longest prefix of s containing at most k distinct characters.
Delete the prefix from s and increase the number of partitions by one.
The remaining characters (if any) maintain their initial order.

Return an integer denoting the maximum number of resulting partitions after the operations by optimally choosing at most one character to change.

Input & Output

Example 1 — Basic Case

$ Input: s = "accca", k = 2

› Output: 3

💡 Note: Without change: "ac|cc|a" gives 3 partitions. With optimal change s[4]='c': "ac|cc|c" still gives 3 partitions. Maximum is 3.

Example 2 — Change Helps

$ Input: s = "aabaaca", k = 3

› Output: 5

💡 Note: Without change: "aabaa|ca" gives 2 partitions. Change s[2]='c': "aa|c|aa|c|a" gives 5 partitions.

Example 3 — Small k

$ Input: s = "abcdef", k = 1

› Output: 6

💡 Note: Each character forms its own partition since k=1. Total: 6 partitions regardless of changes.

Constraints

1 ≤ s.length ≤ 500
1 ≤ k ≤ 26
s consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

String s="abaca" with k=2 (max 2 distinct chars per partition)

Process

Try changing each character and find optimal partitioning

Output

Maximum number of partitions achievable

Key Takeaway

🎯 Key Insight: Try each possible character change and greedily partition to maximize segments

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is to try changing each character optimally and simulate partitioning. The greedy approach works because we always want the longest possible prefix with ≤ k distinct characters. Best approach uses optimized simulation with O(n² × 26) time and O(k) space for character tracking.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Simulation	O(n² × 26)	O(k)	Try changing each character and simulate partitioning for each possibility
Dynamic Programming with Memoization	O(n × 2^26 × 2)	O(n × 2^26 × 2)	Use recursion with memoization to avoid recomputing the same states
Optimized Dynamic Programming	O(n × k × 2)	O(n × k × 2)	Efficient DP with better state representation and pruning

Brute Force with Simulation — Algorithm Steps

Try no change and each possible character change
For each scenario, simulate partitioning greedily
Track maximum partitions achieved

Visualization

Tap to expand

Step-by-Step Walkthrough

Original String

Count partitions without any changes

Try Changes

For each position and each letter, modify and count partitions

Maximum

Return the highest partition count found

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

int countPartitions(const char* str, int k) {
    int partitions = 0;
    int i = 0;
    int n = strlen(str);
    
    while (i < n) {
        bool chars[26] = {false};
        int distinctCount = 0;
        int j = i;
        
        while (j < n) {
            int charIndex = str[j] - 'a';
            if (!chars[charIndex]) {
                chars[charIndex] = true;
                distinctCount++;
            }
            if (distinctCount > k) {
                break;
            }
            j++;
        }
        partitions++;
        i = j;
    }
    
    return partitions;
}

int solution(char* s, int k) {
    int maxPartitions = countPartitions(s, k);
    int n = strlen(s);
    
    // Try changing each character
    for (int i = 0; i < n; i++) {
        char original = s[i];
        for (char c = 'a'; c <= 'z'; c++) {
            if (c != original) {
                s[i] = c;
                int partitions = countPartitions(s, k);
                if (partitions > maxPartitions) {
                    maxPartitions = partitions;
                }
            }
        }
        s[i] = original;  // restore
    }
    
    return maxPartitions;
}

int main() {
    char s[1001];
    int k;
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;  // remove newline
    scanf("%d", &k);
    printf("%d\n", solution(s, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × 26)

For each of n positions and 26 letters, we simulate O(n) partitioning

⚠ Quadratic Growth

Space Complexity

O(k)

Set to track distinct characters in current partition

✓ Linear Space

8.5K Views

Medium Frequency

~35 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler