Last updated on October 9th, 2024 at 06:13 pm

Here, We see Strange Printer LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Strange Printer LeetCode Solution

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’.

1. Strange Printer LeetCode Solution 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];
    }
};

2. Strange Printer LeetCode Solution 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. Strange Printer Solution 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];
};

4. Strange Printer Solution 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]