Appearance
Flip
Problem Description
You are given a binary string A(i.e. with characters 0 and 1) consisting of characters A1, A2, ..., AN.
In a single operation, you can choose two indices L and R such that 1 ≤ L ≤ R ≤ N and flip the characters AL, AL+1, ..., AR. By flipping, we mean change character 0 to 1 and vice-versa.
Your aim is to perform ATMOST one operation such that in final string number of 1s is maximised.
If you don't want to perform the operation, return an empty array. Else, return an array consisting of two elements denoting L and R. If there are multiple solutions, return the lexicographically smallest pair of L and R.
NOTE: Pair (a, b) is lexicographically smaller than pair (c, d) if a < c or, if a == c and b < d.
Problem Constraints
1 <= size of string <= 1000001 <= size of string <= 100000Input Format
First and only argument is a string A.First and only argument is a string A.Output Format
Return an array of integers denoting the answer.Return an array of integers denoting the answer.Example Input
Input 1:
A = "010"
Input 2:
A = "111"Input 1:
A = "010"
Input 2:
A = "111"Example Output
Output 1:
[1, 1]
Output 2:
[]Output 1:
[1, 1]
Output 2:
[]Example Explanation
Explanation 1:
A = "010"
Pair of [L, R] | Final string
____________|__________
[1 1] | "110"
[1 2] | "100"
[1 3] | "101"
[2 2] | "000"
[2 3] | "001"
We see that two pairs [1, 1] and [1, 3] give same number of 1s in final string. So, we return [1, 1].
Explanation 2:
No operation can give us more than three 1s in final string. So, we return empty array [].Explanation 1:
A = "010"
Pair of [L, R] | Final string
____________|__________
[1 1] | "110"
[1 2] | "100"
[1 3] | "101"
[2 2] | "000"
[2 3] | "001"
We see that two pairs [1, 1] and [1, 3] give same number of 1s in final string. So, we return [1, 1].
Explanation 2:
No operation can give us more than three 1s in final string. So, we return empty array [].Solution
swift
import Foundation
class Solution {
func flip(_ A: inout String) -> [Int] {
// let len = A.count
// var numbers = A.map{$0 == "1" ? 1 : 0}
var l = -1
var r = -1
var w = 0
var curL = -1
var curR = -1
var curW = 0
for (i,c) in Array(A).enumerated(){
if c == "0" {
curW += 1
} else {
curW -= 1
}
if curW < 0 {
curL = -1
curR = -1
curW = 0
continue
}
if curL < 0 {
curL = i
}
curR = i
if curW > w {
l = curL
r = curR
w = curW
}
// if curW == 0 {
// if n == 0 {
// curW += 1
// if curL < 0 {
// curL = i
// }
// curR = i
// if curW > w {
// w = curW
// l = curL
// r = curR
// }
// } else {
// curL = -1
// curR = -1
// }
// } else {
// if n == 0 {
// curW += 1
// curR = i
// if curW > w {
// l = curL
// r = curR
// w = curW
// }
// } else {
// curW -= 1
// curR = i
// }
// }
}
if l < 0 {
return []
}
return [l + 1, r + 1]
// var counter = [(Int,Int)](repeating:(0,0),count:len+1)
// var z = 0
// var o = 0
// for (i,n) in numbers.enumerated() {
// if n == 0 {
// z += 1
// } else {
// o += 1
// }
// counter[i+1] = (z,o)
// }
// var l = -1
// var r = -1
// var w = 0
// for i in 1...len {
// for j in i...len {
// let (jz,jo) = counter[j]
// let (iz,io) = counter[i-1]
// let v = jz - iz - (jo - io)
// if v > w {
// w = v
// l = i
// r = j
// }
// }
// }
// if l < 0 {
// return []
// }
// return [l,r]
}
}import Foundation
class Solution {
func flip(_ A: inout String) -> [Int] {
// let len = A.count
// var numbers = A.map{$0 == "1" ? 1 : 0}
var l = -1
var r = -1
var w = 0
var curL = -1
var curR = -1
var curW = 0
for (i,c) in Array(A).enumerated(){
if c == "0" {
curW += 1
} else {
curW -= 1
}
if curW < 0 {
curL = -1
curR = -1
curW = 0
continue
}
if curL < 0 {
curL = i
}
curR = i
if curW > w {
l = curL
r = curR
w = curW
}
// if curW == 0 {
// if n == 0 {
// curW += 1
// if curL < 0 {
// curL = i
// }
// curR = i
// if curW > w {
// w = curW
// l = curL
// r = curR
// }
// } else {
// curL = -1
// curR = -1
// }
// } else {
// if n == 0 {
// curW += 1
// curR = i
// if curW > w {
// l = curL
// r = curR
// w = curW
// }
// } else {
// curW -= 1
// curR = i
// }
// }
}
if l < 0 {
return []
}
return [l + 1, r + 1]
// var counter = [(Int,Int)](repeating:(0,0),count:len+1)
// var z = 0
// var o = 0
// for (i,n) in numbers.enumerated() {
// if n == 0 {
// z += 1
// } else {
// o += 1
// }
// counter[i+1] = (z,o)
// }
// var l = -1
// var r = -1
// var w = 0
// for i in 1...len {
// for j in i...len {
// let (jz,jo) = counter[j]
// let (iz,io) = counter[i-1]
// let v = jz - iz - (jo - io)
// if v > w {
// w = v
// l = i
// r = j
// }
// }
// }
// if l < 0 {
// return []
// }
// return [l,r]
}
}