Find Shortest String After Removing Different Adjacent Bits in Python

Suppose we have a binary string s, we can delete any two adjacent letters if they are different. Finally, we have to find the length of the smallest string that we can get if we are able to perform this operation as many times as we want.

So, if the input is like s = "1100011", then the output will be 1, as After deleting "10" we get "10011", then again delete "10", it will be "011", then delete "01", it will have left 1.

To solve this, we will follow these steps −

• stack := a new list
• for each c in s, do
  • if stack is empty or top of stack is same as c, then
    • push c into stack
  • otherwise when top of stack is not same as c, then
    • pop element from stack
• return element count in stack

Let us see the following implementation to get better understanding −

Example

 Live Demo

class Solution:
   def solve(self, s):
      stack = []
      for c in s:
         if not stack or stack[-1] == c:
            stack.append(c)
         elif stack[-1] != c:
            stack.pop()
      return len(stack)
ob = Solution() print(ob.solve("1100011"))

Input

"1100011"

Output

1