- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Suppose we have a binary string s. If we can swap at most one pair of characters in the string, we have to find the resulting length of the longest contiguous substring of 1s.

So, if the input is like s = "1111011111", then the output will be 9, as we can swap s[4] and s[9] to get 9 consecutive 1s.

To solve this, we will follow these steps −

- l := 0, cnt := 0, ans := 0
- for r in range 0 to size of s, do
- cnt := cnt + (1 when s[r] is same as "0" otherwise 0)
- if cnt > 1, then
- cnt := cnt - (1 when s[l] is same as "0" otherwise 0)
- l := l + 1

- ans := maximum of ans and (r - l + 1)

- return minimum of ans and occurrence of 1 in s

Let us see the following implementation to get better understanding −

class Solution: def solve(self, s): l = 0 cnt = 0 ans = 0 for r in range(len(s)): cnt += s[r] == "0" if cnt > 1: cnt -= s[l] == "0" l += 1 ans = max(ans, r - l + 1) return min(ans, s.count("1")) ob = Solution() s = "1111011111" print(ob.solve(s))

"1111011111"

9

- Related Questions & Answers
- Program to find longest subarray of 1s after deleting one element using Python
- Program to find length of longest set of 1s by flipping k bits in Python
- Program to find longest distance of 1s in binary form of a number using Python
- Program to maximize the number of equivalent pairs after swapping in Python
- Program to find number of substrings with only 1s using Python
- Program to find length of longest palindromic substring after single rotation in Python
- Program to find number of boxes that form longest chain in Python?
- Program to find number of sublists containing maximum and minimum after deleting only one element in Python
- Program to find longest equivalent sublist after K increments in Python
- Program to find shortest string after removing different adjacent bits in Python
- Number of 1 Bits in Python
- Program to find higher number with same number of set bits as n in Python?\n
- Find a pair of elements swapping which makes sum of two arrays same in C++
- Python program to reverse bits of a positive integer number?
- Program to find number of items left after selling n items in python

Advertisements