Cheapest Flips to Make Two Binary Strings Equal
Updated
Problem statement
You have two binary strings a and b of the same length n, and a price x. You want to change a until it equals b. To flip a character means to change '0' to '1' or '1' to '0'. Two moves are allowed, as many times as you like and in any order:
- Pick any two different positions
iandjand flip botha[i]anda[j]. This costsx. - Pick a position
iwithi + 1 < nand flip botha[i]anda[i + 1]. This costs1.
Return the smallest total cost that makes a equal to b, or -1 if it cannot be done.
Function
minFlipCost(a: String, b: String, x: int) → intExamples
Example 1
a = "0110010"b = "1010001"x = 3return = 2The strings differ at positions 0, 1, 5 and 6. Flip neighbors 0 and 1 (cost 1) and neighbors 5 and 6 (cost 1): total 2.
Example 2
a = "10000001"b = "00000000"x = 2return = 2They differ only at positions 0 and 7. Walking the change along with neighbor flips would cost 7, but one flip of the pair (0, 7) costs x = 2.
Example 3
a = "111"b = "000"x = 5return = -1All three positions differ. Every flip changes two characters, so the number of differences always stays odd and can never reach 0: the answer is -1.
Constraints
1 <= a.length == b.length <= 2000aandbcontain only'0'and'1'1 <= x <= 1000
More Adobe Phone Screen questions
- Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
- All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
- Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
- Binary Tree Level-Order Traversal by LevelsPHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2026
- Count Occurrences in a Sorted ArrayPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
- Count Pairs with Absolute Difference KPHONE SCREEN · Seen Jul 2026
- Count Subsets with Sum KPHONE SCREEN · Seen Jul 2026
- Numbers with Exactly Three DivisorsPHONE SCREEN · Seen Jul 2026
- Sum of Even Nodes on a Path in a Numbered Binary TreePHONE SCREEN · Seen Jul 2026
- Largest Value in Every Sliding WindowPHONE SCREEN · Seen Jul 2026
Similar questions at other companies
- Longest Palindromic SubstringSiemens · PHONE SCREEN
- Query Words Within K PositionsPalantir · PHONE SCREENPalantir interview questions
- Edit DistanceDP World · PHONE SCREEN
- Longest Palindromic SubstringIBM · PHONE SCREENIBM interview questions
- Word BreakAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Decode WaysThe D.E. Shaw Group · PHONE SCREENThe D.E. Shaw Group interview questions
- Edit DistanceAstrotalk · PHONE SCREEN
- Longest Palindromic SubstringeBay · PHONE SCREENeBay interview questions
- Validate a Palindrome After Limited DeletionsMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
- Count Palindromic SubstringsThe Voleon Group · PHONE SCREEN