0

Longest proper prefix that is also a suffix

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Longest proper prefix that is also a suffix

Companies: Microsoft

Difficulty: Medium

Problem statement

Given a string s, return the length of the longest string that is both a proper prefix and a proper suffix of s.

  • A prefix is a run of characters at the start of s; a suffix is a run at the end.
  • Proper means the whole string does not count. So the answer is always less than len(s).
  • The prefix and the suffix may overlap inside s.
  • If no such non-empty string exists, return 0.

Implement:

def longest_prefix_suffix(s: str) -> int: ...

Constraints

  • 0 <= len(s) <= 10^5
  • s contains lowercase English letters.
  • Aim for better than O(n^2) time.

Examples

Example 1

Input:  s = "abcabcab"
Output: 5

"abcab" is the first five characters and also the last five. The two copies overlap in the middle.

Example 2

Input:  s = "pqrs"
Output: 0

No non-empty proper prefix matches the suffix of the same length.

Approach

You want the longest string that is both a proper prefix and a proper suffix of s. People call this a "border" of s. The answer is a length, and it is always less than len(s).

Brute force. Try every length L from n - 1 down to 1. Return the first L where s[:L] == s[n - L:]. Each check costs O(L), so the worst case is O(n²). An input like "aaaa...ab" hits that bound. Say this first, then say why it repeats work: each failed check throws away everything it learned about matching characters.

KMP prefix function (the expected answer). Build pi, where pi[i] is the length of the longest proper border of s[:i + 1]. The answer is pi[n - 1].

  • Keep k = pi[i - 1], the length of the current border of the previous prefix.
  • To extend it to position i, compare s[i] with s[k]. If they match, pi[i] = k + 1.
  • If they do not match, fall back to the next shorter border: k = pi[k - 1]. A border of a border is also a border, so this visits every candidate in decreasing length and skips none.
  • If k reaches 0 and s[0] != s[i], then pi[i] = 0.

Why it is O(n): k goes up by at most 1 per character, and every fallback makes it smaller. Total fallbacks cannot exceed total increases, so the loop does at most 2n comparisons.

Alternative: rolling hash. Keep a hash of the growing prefix and the growing suffix together. Record the largest L < n where the two hashes agree. That is also O(n), but a hash collision can give a wrong answer unless you verify the match or use two moduli. Mention it, then pick KMP because it is exact.

Invariants to state out loud:

  • pi[i] < i + 1, so the border is always proper.
  • After processing index i, k == pi[i].

Code

from typing import List


def prefix_function(s: str) -> List[int]:
    """pi[i] = length of the longest proper prefix of s[:i+1] that is also its suffix."""
    n = len(s)
    pi = [0] * n
    k = 0
    for i in range(1, n):
        while k > 0 and s[i] != s[k]:
            k = pi[k - 1]          # fall back to the next shorter border
        if s[i] == s[k]:
            k += 1
        pi[i] = k
    return pi


def longest_prefix_suffix(s: str) -> int:
    """Length of the longest proper prefix of s that is also a suffix."""
    if not s:
        return 0
    return prefix_function(s)[-1]


def longest_prefix_suffix_brute(s: str) -> int:
    """O(n^2) oracle: try every length from longest to shortest."""
    n = len(s)
    for length in range(n - 1, 0, -1):
        if s[:length] == s[n - length:]:
            return length
    return 0


def all_borders(s: str) -> List[int]:
    """Every border length, longest first, by walking the pi chain."""
    if not s:
        return []
    pi = prefix_function(s)
    out: List[int] = []
    k = pi[-1]
    while k > 0:
        out.append(k)
        k = pi[k - 1]
    return out


def shortest_palindrome(s: str) -> str:
    """Follow-up: add the fewest characters in front of s to make a palindrome."""
    combined = s + "#" + s[::-1]
    keep = prefix_function(combined)[-1]   # longest palindromic prefix of s
    return s[keep:][::-1] + s


if __name__ == "__main__":
    import random

    assert longest_prefix_suffix("") == 0
    assert longest_prefix_suffix("z") == 0
    assert longest_prefix_suffix("zz") == 1
    assert longest_prefix_suffix("abcab") == 2
    assert longest_prefix_suffix("abcabcab") == 5
    assert longest_prefix_suffix("pqrs") == 0
    assert longest_prefix_suffix("aaaa") == 3
    assert longest_prefix_suffix("aabaaab") == 3
    assert all_borders("abacaba") == [3, 1]
    assert shortest_palindrome("aacecaaa") == "aaacecaaa"
    assert shortest_palindrome("abcd") == "dcbabcd"

    for _ in range(2000):
        t = "".join(random.choice("ab") for _ in range(random.randint(0, 12)))
        assert longest_prefix_suffix(t) == longest_prefix_suffix_brute(t), t
    print("ok")

Complexity

  • prefix_function / longest_prefix_suffix: O(n) time, O(n) space for the pi array. The while loop is amortized: k rises at most n times in total, so it can fall at most n times.
  • Brute force: O(n²) time in the worst case, O(n) space for the slices (O(1) with an index-by-index compare).
  • all_borders: O(n) to build pi, plus O(number of borders) to walk the chain.
  • Rolling-hash variant: O(n) time, O(1) extra space, but only correct with high probability unless matches are verified.

Test cases

  • "" -> 0 (empty string has no proper prefix).
  • "z" -> 0 (the only prefix is the whole string, which is not proper).
  • "zz" -> 1.
  • "abcab" -> 2 ("ab").
  • "abcabcab" -> 5 ("abcab"; borders can overlap).
  • "pqrs" -> 0.
  • "aaaa" -> 3 (overlapping run of one letter).
  • "aabaaab" -> 3 ("aab"; needs one fallback while building pi).
  • "abacaba" -> 3; all borders are [3, 1].
  • Random strings over {a, b} of length 0-12 agree with the brute force.
  • Large input, "a" * 10**5 + "b" -> 0, and it must finish fast (it is the brute force's worst case).

Follow-ups

  1. List every border, or count them. Walk the chain pi[n-1], pi[pi[n-1]-1], ... until it reaches 0. No new pass over the string is needed.
  2. Shortest palindrome by adding characters in front. Run the prefix function on s + "#" + reverse(s). The last value is the longest palindromic prefix of s. Reverse the rest and put it in front. The separator stops a border from running past the middle.
  3. Find all occurrences of a pattern p in a text t. Run the prefix function on p + "#" + t, or keep pi for p and stream t through the same fallback loop. Every position where the value equals len(p) is a match end. This is O(|p| + |t|).
  4. Smallest period / is the string a repetition of a block? The smallest period is n - pi[n-1]. The string is a whole repetition of a block exactly when that period divides n (and the period is less than n).
  5. Strings too big for memory, or many queries. For streaming, keep only pi of the pattern and the current k. For many "longest border of this substring" queries, move to Z-function, suffix structures, or hashing with binary search, and discuss the trade-offs.

Interviewer expectations

Mid-level (L4)

  • States what "proper" excludes and handles empty and one-character strings.
  • Writes the brute force correctly, then reaches the prefix function with some hints.
  • Code runs and passes the given examples, including overlapping borders like "aaaa".

Senior (L5)

  • Goes straight to the prefix function and explains the fallback k = pi[k - 1] without hints.
  • Gives the amortized argument for O(n) instead of claiming it.
  • Names a brute-force worst case, tests against a brute-force oracle, and handles one or two follow-ups (periods, pattern search) cleanly.

Staff (L6+)

  • Compares KMP, Z-function, and rolling hash, including collision risk and how to remove it.
  • Applies the same pi chain to several follow-ups (all borders, shortest palindrome, periodicity) without new machinery.
  • Discusses streaming and very large inputs: what state must stay in memory and how the design changes for many substring queries.

Sign in to comment, vote or remix.