Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

python
binary
subsets
communitycreator

How to sort a binary string by flipping bits of substrings

Dhruv Sharma

The problem statement

Given a binary string, sort the string by repeatedly flipping 0s and 1s of a subset of the string, making sure the size of the substring is different in each flip. For each flip, print the length of the substring and print the sorted string.

For example, for a given string 110110111:

  • Flip indexes 0 to 5, a substring of length 6. The string is now 001001111.
  • Flip indexes 2 to 4, a substring of length 3. The string is now 000111111.

The string is now sorted.

Code

string = "110110111"
string = list(string)
length = len(string)

i,j = 0,length-1

if string.count('1') != 0 and string.count('0') != 0:
    while i != j + 1:
        k = i
        while k < length:
            if(string[k] == '1'):
                i = k
                break
            k += 1

        u = j
        while u >= 0:
            if(string[u] == '0'):
                j = u
                break
            u -= 1

        ti = i
        while(ti <= j):
            if string[ti] == '0':
                string[ti] = '1'
            else:
                string[ti] = '0'
            ti += 1

        if j + 1 - i != 0:
            print(j + 1 - i)

print(''.join(string))
Sorting a binary string by flipping bits of substrings

Explanation

  • Line 2: We convert the given string to a list of all characters.
  • Line 3: We initialize a variable called length, which holds the length of the string.
  • Line 5: We initialize the variables i and j, which initially hold the indexes of the start and end points of the string. i and j are used later to hold the indexes of the first 1 and the last 0, respectively.
  • Line 7: We check  string.count('1') != 0 and string.count('0') != 0 before running the sorting loop, as a string with all zeros or all ones is already sorted.
  • Line 8: We run the sorting loop while i != j+1, because when the index of the last 0 occurs after the index of the first 1, the string becomes sorted, as is demonstrated below:
    • For the string 00010111:
      • i = 3 and j = 4
      • The string is not sorted.
    • For the string 00001111:
      • i = 4 and j = 3
      • The string is sorted.
  • Lines 9–14: We initialize a variable k, which holds the value of i in the last iteration. We loop through the string, checking each element after k until we find the index of the next 1. Then, we change the value of i to k.
  • Lines 16–21: We initialize a variable u, which holds the value of j in the last iteration. We loop through the string, checking each element before j until we find the index of the last 0. Then, we change the value of j to u.
  • Lines 23–29: We initialize a variable ti, which holds the value of i and iterate through elements from i to j. For each element, we flip the values of 1 and 0.
  • Lines 31–32: We print j+1-i, which is the length of the substring. We do not print anything if the length of the substring is 0, because the string is already sorted in that case.
  • Line 34: We print the sorted string.

Dry running the code

For the string 110110111:

Iteration

Value of i

Value of j

String after iteration

1

0

5

001001111

2

2

4

000111111

3

3

2

000111111

RELATED TAGS

python
binary
subsets
communitycreator
RELATED COURSES

View all Courses

Keep Exploring