Password similarity under cyclic character bumps: Frontier Interview's solution

Question: Password similarity under cyclic character bumps

Companies: Amazon

Difficulty: Medium

Problem statement

A security team wants to reject a new password when it is too close to the user's previous one.

You may transform the new password like this: pick any set of its positions (possibly none) and replace each chosen character with the next letter of the alphabet, cyclically (a becomes b, m becomes n, z becomes a). Each position is bumped at most once.

The two passwords are similar if, for some choice of positions, the old password is a subsequence of the transformed new password. A subsequence keeps the original order but may skip characters.

You are given two lists of the same length, new_passwords and old_passwords. For each index i, decide whether new_passwords[i] and old_passwords[i] are similar.

Implement check_similarities(new_passwords: list[str], old_passwords: list[str]) -> list[str], returning "YES" or "NO" for each pair.

Constraints

1 <= len(new_passwords) == len(old_passwords) <= 10
1 <= len(new_passwords[i]), len(old_passwords[i]) <= 2 * 10^5
All passwords contain only lowercase English letters.

Example 1

new_passwords = ["abdbc"], old_passwords = ["bcd"]
Output: ["YES"]

Bump the first a to b and the following b to c, giving bcdbc. The first three characters spell bcd.

Example 2

new_passwords = ["aaa", "zb"], old_passwords = ["c", "ab"]
Output: ["NO", "YES"]

An a can only become a or b, so c never appears. In the second pair, z wraps around to a and b stays, giving ab.

Approach

Each character of the new password can stay as it is or move one step
forward on the cyclic alphabet (z wraps to a). The question is whether
some choice of those moves turns the old password into a subsequence of the
new one.

Brute force. Try every subset of positions to bump, then run a normal
subsequence check. That is O(2^n · (n + m)) and is only useful to state the
search space out loud.

Key observation. The choices are independent per character, so we never
have to fix them up front. Read the new password once and ask, for each
character c, "can c (or next(c)) be the next letter of the old password
that we still need?" If yes, use it and advance the pointer into the old
password. If no, skip it.

Why greedy matching is safe. This is the standard subsequence argument.
Suppose an optimal matching pairs old[j] with some later position of the new
password, while the current position i could also match old[j]. Moving
that pair back to i keeps every later pair valid, because they all sit
after i anyway. So taking the earliest possible match never loses. Each
new-password position is a free choice that does not affect other positions,
which is what makes the exchange work.

Invariants

j is the length of the longest prefix of old that can be matched inside
new[:i].
j only moves forward, and each step of i costs O(1).
The answer is "YES" exactly when j == len(old) at the end.

Early exits: if len(old) > len(new), the answer is "NO" at once. If old
is empty, the answer is "YES".

The task usually arrives as two parallel lists of passwords. Answer each pair
on its own and return a list of "YES" / "NO" strings.

Code

from typing import List


def next_char(c: str) -> str:
    """Next letter on the cyclic lowercase alphabet: 'a'->'b', 'z'->'a'."""
    return "a" if c == "z" else chr(ord(c) + 1)


def is_similar(new_password: str, old_password: str) -> bool:
    """True if old_password is a subsequence of new_password after
    optionally bumping any characters of new_password to their next letter."""
    m = len(old_password)
    if m == 0:
        return True
    if m > len(new_password):
        return False

    j = 0  # next index of old_password we still need
    for c in new_password:
        target = old_password[j]
        if c == target or next_char(c) == target:
            j += 1
            if j == m:
                return True
    return False


def check_similarities(new_passwords: List[str], old_passwords: List[str]) -> List[str]:
    """Answer each (new, old) pair with 'YES' or 'NO'."""
    if len(new_passwords) != len(old_passwords):
        raise ValueError("password lists must have the same length")
    return [
        "YES" if is_similar(new, old) else "NO"
        for new, old in zip(new_passwords, old_passwords)
    ]


# --- Follow-up: each character may move up to k steps forward. ---

def is_similar_k(new_password: str, old_password: str, k: int) -> bool:
    """Same greedy, but a character c can become any of c, c+1, ..., c+k (mod 26)."""
    k = min(k, 25)  # 25 steps already reach every letter
    j, m = 0, len(old_password)
    if m == 0:
        return True
    for c in new_password:
        shift = (ord(old_password[j]) - ord(c)) % 26
        if shift <= k:
            j += 1
            if j == m:
                return True
    return False


if __name__ == "__main__":
    assert is_similar("abdbc", "bcd")          # a->b, b->c, d
    assert is_similar("zza", "ab")             # z->a, then a->b
    assert not is_similar("aaa", "c")          # 'a' reaches only 'a' or 'b'
    assert is_similar("xyz", "")               # empty old password
    assert not is_similar("ab", "abc")         # old longer than new
    assert is_similar("zb", "ab")              # z wraps to a
    assert not is_similar("ba", "ab")          # order matters
    assert check_similarities(["aaccbbee", "aab"], ["bdbf", "aee"]) == ["YES", "NO"]
    assert is_similar_k("aaa", "c", 2)
    assert not is_similar_k("aaa", "d", 2)
    assert is_similar_k("y", "b", 3)           # y->z->a->b
    print("all tests passed")

Complexity

is_similar: O(n) time for a new password of length n (one pass, O(1)
work per character). O(1) extra space.
check_similarities: O(sum of new-password lengths) time. O(q) space for
the q answers.
is_similar_k: O(n) time and O(1) space; the shift test is one modular
subtraction.

Test cases

new = "abdbc", old = "bcd" -> YES (a->b, b->c, d kept).
new = "aaa", old = "c" -> NO (a can only become a or b).
new = "zb", old = "ab" -> YES (z wraps to a, b kept).
new = "ba", old = "ab" -> NO (order of the subsequence matters).
new = "xyz", old = "" -> YES (empty old password is always a subsequence).
new = "ab", old = "abc" -> NO (old password longer than new).
new = "abc", old = "abc" -> YES (identical strings, no bumps needed).
Batch: new = ["aaccbbee", "aab"], old = ["bdbf", "aee"] -> ["YES", "NO"].
Large: new = "a" * 10**5, old = "b" * 10**5 -> YES in linear time.

Follow-ups

Up to k forward steps per character. Replace the equality test with
(old[j] - c) mod 26 <= k. The greedy argument is unchanged because each
position is still an independent choice. Shown as is_similar_k.
Return the transformation, not just yes/no. Record the index of new
used for each old[j] and whether it was bumped. This gives a witness that
a reviewer can check. Same O(n) time, O(m) extra space.
Minimum number of bumps. Greedy earliest match no longer minimizes the
count, since a later exact match may avoid a bump. Use DP over
(i, j) with cost 0 for an exact match and 1 for a bumped match:
O(n · m) time, O(m) space with a rolling row.
One new password, many old passwords. Build a next-occurrence table
nxt[i][ch] for the new password in O(26 · n). Each query then jumps to
min(nxt[i][old[j]], nxt[i][prev(old[j])]) per character, so a query
costs O(m) instead of O(n).
Full character set (digits, upper case). Define next_char per class
(9->0, Z->A) or by an explicit mapping. Only the helper changes.

Interviewer expectations

Mid-level (L4)

Recognizes the subsequence check and writes the two-pointer greedy without
hints.
Handles the z -> a wrap and the empty / too-long old password edge cases.
States O(n) time and O(1) space per pair.

Senior (L5)

Explains why taking the earliest match is safe (exchange argument), and
why per-position independence matters.
Extends cleanly to k steps with modular arithmetic and gives tests for
the wrap.
Notes that minimum-bumps breaks the greedy and switches to DP.

Staff (L6+)

Discusses the batch shape: preprocessing the new password for many queries,
and the trade-off of the O(26 · n) table.
Connects the check to the real policy concern (similarity rules, comparing
against hashed history, why you can only run this at password-change time
when both plaintexts are present).
Keeps the code generic over the "allowed transformation" so new policies
plug in without rewriting the matcher.