Skip to content

← leetcode

Minimum Length of String After Operations

· Medium

LeetCode problem 3223

This question looks a lot more complicated than it actually is.

The trick is that, in string s, if a character appears:

  • an odd number of times, then we will be able to keep minimum 1 character
  • an even number of times, then we will be able to keep minimum 2 characters

(you can easily demonstrate this using an example)

Since there are only 26 letters in the alphabet, we can keep track of this data in an integer array length 26 while we iterate through the string s.

code

class Solution {
public:
    int minimumLength(string s) {
        int alphabet[26] = {0};
        for (char c : s) {
            if (alphabet[c-'a'] == 0) {
                ++alphabet[c-'a'];
            } else {
                alphabet[c-'a'] ^= 3;
            };
        }
        int ans = 0;
        for (int i : alphabet) {
            ans += i;
        }
        return ans;
    }
};

complexity

  • Time: O(n)
  • Space: O(1)