Today I have done leetcode's August LeetCoding Challenge with cpp.

August LeetCoding Challenge 21

Description

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.

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
int dp[100][100];
class Solution {
public:
  int strangePrinter(string target) {
    string s;
    s.push_back(target.front());
    for(auto c : target) {
      if(c != s.back()) {
        s.push_back(c);
      }
    }
    int len = s.length();
    for(int l = 0; l < len; ++l) {
      for(int left = 0; left + l < len; ++left) {
        int right = left + l;
        if(!l) {
          dp[left][right] = 1;
        } else {
          dp[left][right] = dp[left][right - 1] + 1;
        }
        for(int middle = left; middle < right; middle += 1) {
          if(s[middle] == s[right]) {
            dp[left][right] = min(dp[left][right], dp[left][middle] + dp[middle + 1][right - 1]);
          }
        }
      }
    }
    return dp[0][len - 1];
  }
};

// Accepted
// 200/200 cases passed (12 ms)
// Your runtime beats 98.86 % of cpp submissions
// Your memory usage beats 66.76 % of cpp submissions (6.3 MB)