0

Fewest append-to-end moves to reverse a binary image

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Fewest append-to-end moves to reverse a binary image

Companies: Amazon

Difficulty: Medium

Problem statement

An image is stored as a binary string s: '1' is a white pixel and '0' is a black pixel. To make a backup, you want to turn s into its reverse, s read from right to left.

You may use one operation any number of times: pick any character of the current string, remove it, and append it at the end.

Implement find_minimum_operations(s: str) -> int. It returns the fewest operations that turn s into its reverse.

Constraints

  • 0 <= len(s) <= 2 * 10^5
  • s contains only '0' and '1'

Example 1

s = "0010"      reverse = "0100"
move index 1 ('0'): "010" + "0" = "0100"
output: 1

Example 2

s = "0001"      reverse = "1000"
output: 3

Only the final '1' can stay where it is relative to the rest. All three '0's have to be moved behind it.

Example 3

s = "0110"      output: 0   (s is already a palindrome)

Approach

Restate the operation first. One move takes a character out of the string and appends it at the end. The target is r = s[::-1]. Because r is a permutation of s, an answer always exists. In the worst case you move every character, in the order of r.

What a sequence of moves looks like. Split the characters into two groups:

  • Kept characters are never moved. They keep their relative order, and once every move is done they form the front of the string.
  • Moved characters sit after the kept ones, in the order you moved them. You choose that order freely.

So the final string is (kept characters, in their original order) followed by (moved characters, in any order you like). Each character only needs to move once: if you move a character twice, the first move does nothing useful.

Brute force. Try every subset of characters to keep. Check that the kept characters, in order, spell a prefix of r, and that the moved ones are the right multiset for the rest. That costs O(2^n · n). You can also run a BFS over strings, one move per edge. Both are fine for checking small cases and too slow for anything else.

Key observation. The kept characters must spell r[:k] for some k, and they must be a subsequence of s. The moved characters then have to spell r[k:]. Their multiset is right automatically: s and r contain the same characters, and the kept ones account for exactly r[:k]. You can put them in the right order by moving them in the order they appear in r[k:]. So:

answer = n − (length of the longest prefix of r that is a subsequence of s)

Finding that prefix greedily. Walk s with an index i and r with an index j. When s[i] == r[j], advance j. Always advance i. At the end, j is the longest prefix length. Matching each character of r at the earliest possible place in s never hurts later matches (the standard subsequence exchange argument), so the greedy is optimal.

Example: s = "0010" gives r = "0100". Greedy matches 0 (i=0), 1 (i=2), 0 (i=3). That is k = 3, and then s runs out. The answer is 4 − 3 = 1: move the 0 at index 1 to the end, which gives "0100".

Invariants.

  • After the loop, r[:j] is a subsequence of s, and r[:j+1] is not.
  • The answer is at most n − 1 for n ≥ 1, because r[0] = s[-1] always matches.
  • The answer is 0 exactly when s is a palindrome.

Nothing here depends on the alphabet being binary. The same code works for any string, and for any target that is an anagram of s.

Code

from collections import Counter
from typing import List


def longest_prefix_subsequence(s: str, target: str) -> int:
    """Length of the longest prefix of target that is a subsequence of s."""
    j = 0
    for ch in s:
        if j < len(target) and ch == target[j]:
            j += 1
    return j


def min_operations_to(s: str, target: str) -> int:
    """Fewest 'remove a char, append it at the end' moves turning s into target.

    Returns -1 when target is not a rearrangement of s.
    """
    if len(s) != len(target) or Counter(s) != Counter(target):
        return -1
    return len(s) - longest_prefix_subsequence(s, target)


def find_minimum_operations(s: str) -> int:
    """Fewest moves that turn s into its own reverse."""
    return min_operations_to(s, s[::-1])


def moves_to(s: str, target: str) -> List[int]:
    """One optimal sequence of moves.

    Each entry is the index, in the string as it is at that moment, of the
    character to remove and append. Assumes target is a rearrangement of s.
    """
    # Mark the characters we keep (greedy earliest match).
    keep = [False] * len(s)
    j = 0
    for i, ch in enumerate(s):
        if j < len(target) and ch == target[j]:
            keep[i] = True
            j += 1
    # Move the rest in the order target[j:] needs them.
    current = list(s)
    alive = keep[:]  # alive[i]: position i is fixed at the front
    moves: List[int] = []
    for ch in target[j:]:
        # Find the first not-yet-moved character equal to ch.
        idx = next(i for i, c in enumerate(current)
                   if not alive[i] and c == ch)
        moves.append(idx)
        current.append(current.pop(idx))
        alive.append(alive.pop(idx))
        alive[-1] = True  # now placed, never touch it again
    assert "".join(current) == target
    return moves


if __name__ == "__main__":
    assert find_minimum_operations("0010") == 1
    assert find_minimum_operations("00110101") == 3
    assert find_minimum_operations("0110") == 0
    assert find_minimum_operations("") == 0
    assert find_minimum_operations("1") == 0
    assert find_minimum_operations("01") == 1
    assert find_minimum_operations("0001") == 3
    assert min_operations_to("abc", "abd") == -1
    assert len(moves_to("00110101", "10101100")) == 3
    print("ok")

Complexity

  • find_minimum_operations: O(n) time. The reverse and the counts take O(n) extra space. With a binary alphabet you can skip the count check and walk s from the back instead of building r, which gives O(1) extra space.
  • moves_to: O(n²) time as written, because of the list pops and the scans. Producing the move list is a follow-up, not the core question. It can be made O(n log n) with a Fenwick tree over positions.

Test cases

  • "0010" → 1 (reverse "0100"; move index 1).
  • "00110101" → 3 (reverse "10101100"; longest matched prefix is "10101", length 5).
  • "0110" → 0 (already a palindrome).
  • "" → 0; "1" → 0.
  • "01" → 1 (move the 0).
  • "0001" → 3 (reverse "1000"; only the final 1 matches, so the three 0s all move).
  • "1111" → 0 (all the same character).
  • "10" → 1.
  • "110100" → 4 (reverse "001011"; the greedy matches only "00", at indices 2 and 4, and no 1 follows them).
  • Large input: "0" * 10**5 + "1" → 10**5. The method is linear, so this is instant.
  • Cross-check: for every binary string up to length 10, the answer equals a BFS over strings with one move per edge.

Follow-ups

  • Any target string. Turn s into an arbitrary t. It is the same formula with t in place of the reverse, plus an anagram check that returns -1 when it fails. min_operations_to already handles this.
  • Move to the front instead. By symmetry, the kept characters form a suffix of the target. Match the target backwards from its end against s backwards. The answer is n − (longest suffix of the target that is a subsequence of s).
  • Moves to either end. Now the kept characters must form a contiguous block target[a:b] that is a subsequence of s. Characters before the block get moved to the front, those after it to the back. Try each start a and match greedily, which is O(n²). Many interviewers accept that; an O(n · |Σ|) version uses next-occurrence tables.
  • Return the moves. See moves_to: keep the greedy-matched characters and move the rest in target order. Say how indices shift after each move. A Fenwick tree makes it O(n log n).
  • Many images, or a stream. Each string is independent and linear, so a batch is O(total length) and easy to parallelize. For a stream, you need the whole string before you know the reverse. Call that out instead of pretending you can do it online.

Interviewer expectations

Mid-level (L4)

  • Notices that each character moves at most once, and that unmoved characters keep their order at the front.
  • Reduces the problem to "longest prefix of the reverse that is a subsequence of s" and codes the two-pointer scan.
  • Tests palindromes, length 0 and 1, and a string that needs n − 1 moves.

Senior (L5)

  • Justifies the reduction both ways: every valid plan keeps such a prefix, and every such prefix gives a plan with exactly that many moves.
  • Explains why the greedy earliest match is optimal, and generalizes to any target, with the anagram check.
  • Verifies against a brute force BFS on small inputs.

Staff (L6+)

  • Handles the variants (prepend, either end, returning the actual moves) by reusing one idea: the kept characters form a block of the target and must be a subsequence of s.
  • Discusses complexity for producing moves (index shifting, Fenwick tree) and memory for huge inputs (scan s backwards instead of building the reverse).
  • Keeps the code small and reads the problem precisely, for example spotting that the binary alphabet doesn't matter.

Sign in to comment, vote or remix.