Strange Printer - Practice Coding Problems

Strange Printer - Problem

There is a strange printer with the following two special properties:

The printer can only print a sequence of the same character each time.
At each turn, the printer can print new characters starting from and ending at any place and will cover the original existing characters.

Given a string s, return the minimum number of turns the printer needed to print it.

Input & Output

Example 1 — Basic Case

$ Input: s = "aba"

› Output: 2

💡 Note: First print 'a' at positions 0 and 2, then print 'b' at position 1. Total: 2 turns.

Example 2 — All Same Characters

$ Input: s = "aaabbb"

› Output: 2

💡 Note: First print 'aaa' (positions 0-2), then print 'bbb' (positions 3-5). Total: 2 turns.

Example 3 — All Different

$ Input: s = "abcd"

› Output: 4

💡 Note: Each character is different, so we need 4 separate printing operations.

Constraints

1 ≤ s.length ≤ 100
s consists of lowercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input String

String 'aba' needs to be printed

Smart Printing

Print matching characters together

Minimum Turns

Find the optimal printing sequence

Key Takeaway

🎯 Key Insight: When characters at the ends match, we can print them together and solve the middle part separately, leading to optimal substructure for dynamic programming.

Asked in

G Google 15 a Amazon 8 f Facebook 6

The key insight is that when the first and last characters of a substring match, we can print them together and solve the middle part separately. The optimal approach uses dynamic programming with a 2D table to build solutions from smaller subproblems. Time: O(n³), Space: O(n²).

Common Approaches

Approach	Time	Space	Notes
✓ Bottom-up Dynamic Programming	O(n³)	O(n²)	Build solution iteratively from smaller subproblems
Dynamic Programming with Memoization	O(n³)	O(n²)	Cache recursive results to avoid redundant calculations
Recursive Brute Force	O(2ⁿ)	O(n)	Try all possible ways to divide the string and take minimum

Bottom-up Dynamic Programming — Algorithm Steps

Initialize DP table with base cases
Fill table for increasing substring lengths
Use optimal substructure to compute each entry

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Base Cases

Single characters need 1 turn

Fill Table Bottom-up

Build solutions for larger substrings

Final Answer

Top-right corner has the answer

Code -

solution.c — C

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

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(char* s) {
    int n = strlen(s);
    if (n == 0) return 0;
    
    int dp[100][100];
    
    // Base case
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }
    
    // Fill for all substring lengths
    for (int length = 2; length <= n; length++) {
        for (int i = 0; i <= n - length; i++) {
            int j = i + length - 1;
            
            dp[i][j] = 1 + dp[i + 1][j];
            
            for (int k = i + 1; k <= j; k++) {
                if (s[k] == s[i]) {
                    dp[i][j] = min(dp[i][j], dp[i][k - 1] + dp[k + 1][j]);
                }
            }
        }
    }
    
    return dp[0][n - 1];
}

int main() {
    char s[100];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops: length, start position, and finding matching characters

⚠ Quadratic Growth

Space Complexity

O(n²)

2D DP table storing results for all substring pairs

⚠ Quadratic Space

28.0K Views

Medium Frequency

~35 min Avg. Time

850 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

Bottom-up Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler