Compute the Shortest String After Delete Different Adjacent Letters

Given a string s consisting only of 1s and 0s, you can delete any two adjacent letters if they are different. Return the length of the smallest string that you can make if you’re able to perform this operation as many times as you want.

Example 1
Input
s = “11000”
Output
1
Explanation
After deleting “10” we get “100” and we can delete another “10” to get “0” which has a length of 1.

Intuitive Bruteforce Simulation Algorithm to Obtain Shortest String After Deletion

As always, we can simulate the process by deleting as many “10” and “01” substring from the original string until we can’t.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int solve(string s) {
    while (true) {
        auto a = s.find("10");
        int res = s.size();
        if (a != string::npos) {
            s.erase(a, 2);
        }
        auto b = s.find("01");
        if (b != string::npos) {
            s.erase(b, 2);
        }
        if (res == s.size()) break;
    }
    return s.size();
}

int solve(string s) {
    while (true) {
        auto a = s.find("10");
        int res = s.size();
        if (a != string::npos) {
            s.erase(a, 2);
        }
        auto b = s.find("01");
        if (b != string::npos) {
            s.erase(b, 2);
        }
        if (res == s.size()) break;
    }
    return s.size();
}

However, this is not efficient as finding the substring and removing it repeatedly takes O(N^2) time.

Math Algorithm to Compute the Diffence

In fact, every 1 will cancel out the 0, and vice versa. Thus, we just have to compute the difference by the number of 1’s and 0’s. This math algorithm takes O(N) time and O(1) constant space.

1
2
3
4
5
6
7

int solve(string s) {
    int a = 0;
    for (const auto &n: s) {
        a += n == '1';
    }
    return abs(a - ((int)s.size() - a));
}

int solve(string s) {
    int a = 0;
    for (const auto &n: s) {
        a += n == '1';
    }
    return abs(a - ((int)s.size() - a));
}

–EOF (The Ultimate Computing & Technology Blog) —