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
拍拍
Thanks!