leetcode

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 };