LeetCode Daily Problem P3228 Maximum Number of Operations to Move 1s to the End

---

Timeline

timeline

2025-11-13

init

greedy

---

Problem:

P3228 Move 1 Maximum Number of Operations to Move to the End

https://leetcode.cn/problems/maximum-number-of-operations-to-move-ones-to-the-end/description/?envType=daily-question&envId=2025-11-13

Maximum number of operations, then start from the leftmost 1, treat adjacent 1s as a group, they are separated by one or more adjacent 0s. Suppose there are n groups of 1s, then it is not difficult to see that the number of operations required to move the i-th group of 1s to the last group of 1s is: the number of 1s in the i-th group * (n-i)

#include <string>
#include <vector>
using std::string;
using std::vector;

class Solution {
    public:
	int maxOperations(string s)
	{
		int i, n = s.size();
		int max_ops = 0;

		int last_1_pos;
		vector<int> vec;
		for (i = 0; i < n; i++) {
			if (s[i] == '1') {
				last_1_pos = i;
				break;
			}
		}
		while (i < n) {
			while (i < n && s[i] == '1') {
				i++;
			}

			vec.push_back(i - last_1_pos);

			while (i < n && s[i] == '0') {
				i++;
			}
			last_1_pos = i;
		}
		if (s.back() == '1' && !vec.empty()) {
			vec.pop_back();
		}
		n = vec.size();
		for (i = 0; i < n; i++) {
			max_ops += vec[i] * (n - i);
		}
		return max_ops;
	}
};