664. Strange Printer

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

Constraints:

• 1 <= s.length <= 100
• s consists of lowercase English letters.

Approach 01:

class Solution {
public:
    int strangePrinter(string s) {
        const int length = s.length();
        vector<vector<int>> memo(length, vector<int>(length));
        
        // Start the recursive function to find the minimum number of turns
        // needed to print the entire string.
        return findMinTurns(s, 0, length - 1, memo);
    }

private:
    // This function returns the minimum number of turns required to print the substring s[start..end].
    int findMinTurns(const string& s, int start, int end, vector<vector<int>>& memo) {
        // Base case: if the start index exceeds the end index, no turns are needed.
        if (start > end)
            return 0;
        
        // If the result for this substring has already been computed, return the cached result.
        if (memo[start][end] > 0){
            return memo[start][end];
        }

        // Initialize the minimum turns by assuming we print the character at 'start' separately.
        memo[start][end] = findMinTurns(s, start + 1, end, memo) + 1;

        // Try to find any matching characters within the range to optimize the number of turns.
        for (int mid = start + 1; mid <= end; ++mid) {
            // If s[mid] matches s[start], consider this as a candidate for reducing the number of turns.
            if (s[mid] == s[start]) {
                memo[start][end] = min(memo[start][end], findMinTurns(s, start, mid - 1, memo) + findMinTurns(s, mid + 1, end, memo));
            }
        }

        // Return the minimum number of turns required to print the substring s[start..end].
        return memo[start][end];
    }
};

class Solution:
    def strangePrinter(self, s: str) -> int:
        length = len(s)
        memo = [[0] * length for _ in range(length)]
        
        # Start the recursive function to find the minimum number of turns
        # needed to print the entire string.
        return self.findMinTurns(s, 0, length - 1, memo)

    def findMinTurns(self, s: str, start: int, end: int, memo: list[list[int]]) -> int:
        # Base case: if the start index exceeds the end index, no turns are needed.
        if start > end:
            return 0
        
        # If the result for this substring has already been computed, return the cached result.
        if memo[start][end] > 0:
            return memo[start][end]

        # Initialize the minimum turns by assuming we print the character at 'start' separately.
        memo[start][end] = self.findMinTurns(s, start + 1, end, memo) + 1

        # Try to find any matching characters within the range to optimize the number of turns.
        for mid in range(start + 1, end + 1):
            # If s[mid] matches s[start], consider this as a candidate for reducing the number of turns.
            if s[mid] == s[start]:
                memo[start][end] = min(memo[start][end], self.findMinTurns(s, start, mid - 1, memo) + self.findMinTurns(s, mid + 1, end, memo))

        # Return the minimum number of turns required to print the substring s[start..end].
        return memo[start][end]

Time Complexity

• Recursive Function Calls:

  The function findMinTurns is recursively called for each possible substring of s. The number of possible substrings of length \( n \) is \( O(n^2) \). For each substring, the function performs a loop to check potential optimizations, leading to a time complexity of \( O(n) \) for each call. Therefore, the overall time complexity for all recursive calls is \( O(n^3) \).

• Memoization:

  Since the results of subproblems are stored in the memo table, each subproblem is solved only once, further contributing to the \( O(n^3) \) time complexity.

• Overall Time Complexity:

  The overall time complexity of the algorithm is \( O(n^3) \), where \( n \) is the length of the string s.

Space Complexity

• Auxiliary Variables:

  The function uses a 2D memoization table memo of size \( n \times n \) to store the results of subproblems, where \( n \) is the length of the string s. The space required for this table is \( O(n^2) \).

• Overall Space Complexity:

  The overall space complexity of the algorithm is \( O(n^2) \) because of the memoization table.