Trusted answers to developer questions
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
iandj, which initially hold the indexes of the start and end points of the string.iandjare used later to hold the indexes of the first1and the last0, respectively. - Line 7: We check
string.count('1') != 0andstring.count('0') != 0before 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 last0occurs after the index of the first1, 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 ofiin the last iteration. We loop through the string, checking each element afterkuntil we find the index of the next1. Then, we change the value ofitok. - Lines 16–21: We initialize a variable
u, which holds the value ofjin the last iteration. We loop through the string, checking each element beforejuntil we find the index of the last0. Then, we change the value ofjtou. - Lines 23–29: We initialize a variable
ti, which holds the value ofiand iterate through elements fromitoj. For each element, we flip the values of1and0. - 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 | Value of | String after iteration |
1 | 0 | 5 | 001001111 |
2 | 2 | 4 | 000111111 |
3 | 3 | 2 | 000111111 |
RELATED TAGS
python
binary
subsets
communitycreator
CONTRIBUTOR
Dhruv Sharma
RELATED COURSES
View all Courses
Keep Exploring
Related Courses
