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*

*List of all LeetCode Solution*

## Topics

Depth-First Search, Dynamic Programming

## Level of Question

Hard

**Strange Printer LeetCode Solution**

## Table of Contents

**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]