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.

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.

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) --

Reposted to Algorithms, Blockchain, and Cloud

Follow me for topics of Algorithms, Blockchain and Cloud.
I am @justyy - a Steem Witness
https://steemyy.com

My contributions

• Steem Blockchain Tools
• Computing & Technology
• Download Youtube Video
• Find Cheap & Bargin VPS: VPS Database
• Online Software and Tools

Support me

If you like my work, please:

• Buy Me a Coffee, Thanks!
• Become my Sponsor, Thanks!
• Voting for me:
  https://steemit.com/~witnesses type in justyy and click VOTE
  
  Alternatively, you could proxy to me if you are too lazy to vote! and you can also vote me at the tool I made: https://steemyy.com/witness-voting/?witness=justyy