leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

2712.cpp (800B)

      1 class Solution {
      2   public:
      3     long long minimumCost(const string &s) const {
      4         static long long dp[100001];
      5 
      6         const int n = size(s);
      7         if (n == 1) return 0;
      8 
      9         dp[0] = 0;
     10         for (int i = 1; i < n; i++) {
     11             dp[i] = s[i] == s[i - 1] ? dp[i - 1] : dp[i - 1] + i;
     12         }
     13 
     14         long long res = LLONG_MAX, acc = 0;
     15         for (int i = n - 2; i >= 0; i--) {
     16             if (s[i] != s[i + 1]) acc += n - i - 1;
     17             res = min(res, dp[i] + acc);
     18         }
     19 
     20         return res;
     21     }
     22 };
     23 
     24 // O(1) space
     25 class Solution {
     26   public:
     27     long long minimumCost(const string &s) const {
     28         long long res = 0;
     29 
     30         for (int i = 1, n = size(s); i < n; i++) {
     31             if (s[i] != s[i - 1]) res += min(i, n - i);
     32         }
     33 
     34         return res;
     35     }
     36 };