leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2712.cpp (800B)

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