Last updated on January 18th, 2025 at 09:53 pm

Here, we see a Strange Printer LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Depth-First Search, Dynamic Programming

Level of Question

Hard

Strange Printer LeetCode Solution

1. Problem Statement

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.

Example 1:
Input: s = “aaabbb”
Output: 2
Explanation: Print “aaa” first and then print “bbb”.

Example 2:
Input: s = “aba”
Output: 2
Explanation: Print “aaa” first and then print “b” from the second place of the string, which will cover the existing character ‘a’.

2. Coding Pattern Used in Solution

The coding pattern used in this code is “Dynamic Programming on Subsequences”. This pattern involves solving problems by breaking them into overlapping subproblems, storing the results of these subproblems in a table (memoization or tabulation), and using these results to build the solution to the original problem.

This specific problem is a variation of Palindromic Subsequence problems, as it involves finding the minimum number of operations to print a string using a “strange printer” that can only print consecutive identical characters in one operation. The solution uses a 2D DP table to store the minimum operations required for each substring.

3. Code Implementation in Different Languages

3.1 Strange Printer C++

class Solution {
public:
    int strangePrinter(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        
        for (int i = n-1; i >= 0; --i) {
            dp[i][i] = 1;
            for (int j = i+1; j < n; ++j) {
                dp[i][j] = dp[i][j-1] + 1;
                for (int k = i; k < j; ++k) {
                    if (s[k] == s[j]) {
                        dp[i][j] = min(dp[i][j], dp[i][k] + (k+1<=j-1 ? dp[k+1][j-1] : 0));
                    }
                }
            }
        }
        return dp[0][n-1];
    }
};

3.2 Strange Printer Java

class Solution {
    public int strangePrinter(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        
        for (int i = n-1; i >= 0; --i) {
            dp[i][i] = 1;
            for (int j = i+1; j < n; ++j) {
                dp[i][j] = dp[i][j-1] + 1;
                for (int k = i; k < j; ++k) {
                    if (s.charAt(k) == s.charAt(j)) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + (k+1<=j-1 ? dp[k+1][j-1] : 0));
                    }
                }
            }
        }
        return dp[0][n-1];
    }
}

3.3 Strange Printer JavaScript

var strangePrinter = function(s) {
    let n = s.length;
    let dp = Array.from(Array(n), () => new Array(n).fill(0));
    for (let i = n-1; i >= 0; --i) {
        dp[i][i] = 1;
        for (let j = i+1; j < n; ++j) {
            dp[i][j] = dp[i][j-1] + 1;
            for (let k = i; k < j; ++k) {
                if (s[k] == s[j]) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + (k+1<=j-1 ? dp[k+1][j-1] : 0));
                }
            }
        }
    }
    return dp[0][n-1];
};

3.4 Strange Printer Python

class Solution(object):
    def strangePrinter(self, s):
        n = len(s)
        dp = [[0]*n for _ in range(n)]
        
        for i in range(n-1, -1, -1):
            dp[i][i] = 1
            for j in range(i+1, n):
                dp[i][j] = dp[i][j-1] + 1
                for k in range(i, j):
                    if s[k] == s[j]:
                        dp[i][j] = min(dp[i][j], dp[i][k] + (dp[k+1][j-1] if k+1<=j-1 else 0))

        return dp[0][n-1]

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n³)	O(n²)
Java	O(n³)	O(n²)
JavaScript	O(n³)	O(n²)
Python	O(n³)	O(n²)

The problem is solved using Dynamic Programming with a 2D DP table.
The time complexity is O(n³) due to the three nested loops.
The space complexity is O(n²) due to the 2D DP table.
The approach is efficient for small to medium-sized strings but may become computationally expensive for very large strings due to the cubic time complexity.