Log inSign up
mediumgeeksforgeeksNot Started

Longest Prefix Suffix

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on geeksforgeeks
Lesson

Problem Statement

Given a string s, find the length of the longest proper prefix which is also a suffix.

Note: Prefix and suffix can be overlapping but they should not be equal to the entire string.

Example 1 · Example:

Input: s = "abab"
Output: 2
Explanation: "ab" is the longest proper prefix that is also a suffix.

Example 2 · Example:

Input: s = "aaaa"
Output: 3
Explanation: "aaa" is the longest proper prefix that is also a suffix.

Example 3 · Example:

Input: s = "abc"
Output: 0
Explanation: There is no common non-empty proper prefix and suffix.

Constraints:

  • 1 <= s.length <= 105
  • s consists of lowercase English alphabets.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the exact LPS array computation loop in KMP.
  • Understand why lps[n - 1] represents the longest proper prefix suffix.
  • Formulate rolling hash and linear state machine alternatives.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding self-overlapping prefixes and suffixes.
  • Calculating minimum characters to append/prepend for palindromes or periods.

Algorithmic Decision Tree:

  • KMP LPS Preprocessing
  • String Periodicity

Connected Patterns:

KMP Pattern MatchingRepeated Substring PatternShortest Palindrome

1. Naive Slicing from Length N-1 Downward

Intuition

Iterate candidate prefix length k from n - 1 down to 1. Compare the prefix s[0...k-1] with the suffix s[n-k...n-1]. The first k that matches is the longest proper prefix suffix, so return k. If no match found, return 0.

When to apply: Basic baseline comparison.

Algorithm

  1. Loop k from n - 1 down to 1:
  2. If s.substr(0, k) == s.substr(n - k, k):
  3. Return k.
  4. Return 0.

Naive Slicing from Length N-1 Downward

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, b, a, b, a, b]
Current operationSTEP 1 OF 6
Observation: A proper prefix or suffix cannot equal the entire string
Visual state
Values and pointers at this exact step
array
S
a
b
a
b
a
b
0
↑ PREFIX [0..4]
1
↑ SUFFIX [1..5]
2
3
4
5
Variables at this step
N
6
candidateLen
5
prefix
ababa
suffix
babab
match
false
Check / comparison
Test length len = N - 1 = 5. Prefix: 'ababa', Suffix: 'babab'.
Decision / next transition
'ababa' != 'babab'. Mismatch; decrement len to 4.
Why this step matters

Observation: A proper prefix or suffix cannot equal the entire string. Maximum possible candidate length is N - 1 = 5.

Decision: Slice prefix s[0..4] = 'ababa' and suffix s[1..5] = 'babab'. Characters mismatch at index 0 (a vs b).

Invariant: Proper prefix and suffix exclude the full string of length N.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 int lps(std::string s) {
7 int n = s.size();
8 for (int len = n - 1; len >= 1; --len) {
9 if (s.substr(0, len) == s.substr(n - len, len)) {
10 return len;
11 }
12 }
13 return 0;
14 }
15};
16
17int main() {
18 Solution sol;
19 std::cout << sol.lps("abab") << std::endl; // 2
20 std::cout << sol.lps("aaaa") << std::endl; // 3
21 std::cout << sol.lps("abc") << std::endl; // 0
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(N^2) — Tests up to N candidate lengths, each string comparison taking up to O(N) operations.
  • Space complexity: O(1) auxiliary

Why Brute Force Doesn't Scale:

Linear 2N amortized step count replaces the quadratic N2 brute force.

Preallocates a single contiguous integer array of size N.

2. Rolling Polynomial Hash Comparison

Intuition

Maintain a forward prefix hash and a backward suffix hash using base 26 and a large prime modulo (e.g. 109 + 7). Iterate i from 0 to n - 2: update prefixHash = (prefixHash * B + s[i]) % MOD and suffixHash = (suffixHash + s[n - 1 - i] * power) % MOD. Whenever prefixHash == suffixHash, record i + 1 as candidate maximum length.

When to apply: When computing prefix-suffix equality without extra array allocations.

Algorithm

  1. Initialize pHash = 0, sHash = 0, power = 1, maxLen = 0.
  2. Loop i from 0 to n - 2:
  3. pHash = (pHash * 26 + (s[i] - 'a')) % MOD
  4. sHash = (sHash + (s[n - 1 - i] - 'a') * power) % MOD
  5. power = (power * 26) % MOD
  6. If pHash == sHash: maxLen = i + 1.
  7. Return maxLen.

Rolling Polynomial Hash Comparison

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, b, a, b, a, b]
Current operationSTEP 1 OF 6
Observation: Use base $P = 31$ and modulo $M = 10^9+7$
Visual state
Values and pointers at this exact step
array
S
a
b
a
b
a
b
0
↑ Hp: s[0]='a'
1
2
3
4
5
↑ Hs: s[5]='b'
Variables at this step
len
1
Hp
1
Hs
2
match
false
maxLps
0
Check / comparison
Length 1: Prefix char 'a' (code 1), Suffix char 'b' (code 2).
Decision / next transition
Hp != Hs (1 != 2). No match at length 1.
Why this step matters

Observation: Use base P = 31 and modulo M = 109+7. Prefix hash advances left-to-right; suffix hash prepends from right-to-left.

Decision: At length 1: H_p = 1, H_s = 2. Hashes differ; no match.

Invariant: Rolling hash computes substring equality in O(1) operations.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 int lps(std::string s) {
7 int n = s.size();
8 if (n <= 1) return 0;
9
10 long long MOD = 1000000007;
11 long long base = 31;
12 long long pHash = 0, sHash = 0, power = 1;
13 int maxLen = 0;
14
15 for (int i = 0; i < n - 1; ++i) {
16 pHash = (pHash * base + (s[i] - 'a' + 1)) % MOD;
17 sHash = (sHash + (s[n - 1 - i] - 'a' + 1) * power) % MOD;
18 power = (power * base) % MOD;
19
20 if (pHash == sHash) {
21 maxLen = i + 1;
22 }
23 }
24 return maxLen;
25 }
26};
27
28int main() {
29 Solution sol;
30 std::cout << sol.lps("abab") << std::endl; // 2
31 std::cout << sol.lps("aaaa") << std::endl; // 3
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(N) — Calculates running polynomial hashes in a single pass of N steps.
  • Space complexity: O(1) extra space

3. KMP LPS Table Construction (Strictly O(N))

Intuition

Initialize lps array of size N with zeros. Maintain len = 0 (length of current matching proper prefix) and pointer i = 1. If s[i] == s[len], increment len, set lps[i] = len, and increment i. If mismatch occurs: if len > 0, fall back len = lps[len - 1]; else set lps[i] = 0 and increment i. At the end of the loop, return lps[n - 1].

When to apply: The standard canonical optimal solution.

Algorithm

  1. Initialize lps array of size n with 0.
  2. Set len = 0, i = 1.
  3. While i < n:
  4. If s[i] == s[len]:
  5. len++
  6. lps[i] = len
  7. i++
  8. Else:
  9. If len != 0: len = lps[len - 1].
  10. Else: lps[i] = 0, i++.
  11. Return lps[n - 1].

KMP LPS Table Construction Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, b, a, b]
Current operationSTEP 1 OF 6
Observation: Base case: proper prefix for single character s[0] is empty
Visual state
Values and pointers at this exact step
array
S
a
b
a
b
0
↑ i=0: lps[0]=0
1
2
3
Variables at this step
i
1
len
0
lps
[0,0,0,0]
Why this step matters

Observation: Base case: proper prefix for single character s[0] is empty.

Decision: lps[0] = 0. Pointers: len = 0, scan index i = 1.

Invariant: lps[i] holds length of longest proper prefix that is also a suffix for s[0..i].

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 int lps(std::string s) {
8 int n = s.size();
9 if (n <= 1) return 0;
10
11 std::vector<int> lps(n, 0);
12 int len = 0, i = 1;
13
14 while (i < n) {
15 if (s[i] == s[len]) {
16 len++;
17 lps[i] = len;
18 i++;
19 } else {
20 if (len != 0) {
21 len = lps[len - 1];
22 } else {
23 lps[i] = 0;
24 i++;
25 }
26 }
27 }
28 return lps[n - 1];
29 }
30};
31
32int main() {
33 Solution sol;
34 std::cout << sol.lps("abab") << std::endl; // 2
35 std::cout << sol.lps("aaaa") << std::endl; // 3
36 std::cout << sol.lps("abc") << std::endl; // 0
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N) strictly — Pointer i advances N times, and len decreases at most N times total, ensuring strict 2N upper bound.
  • Space complexity: O(N) for LPS table

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Naive Quadratic Substring ComparisonO(N^2)O(1)Simple logic.Times out on N = 105.
2.Rolling Polynomial HashO(N)O(1)Calculates prefix and suffix hashes concurrently in a single loop.Requires modular arithmetic and collision verification.
3.KMP LPS Preprocessing (Optimal)OptimalO(N) strictlyO(N) (or O(1) auxiliary variables)Deterministic linear time, industry gold standard.Requires understanding the LPS fallback mechanism.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Incrementing i when falling back len upon mismatch (i must remain stationary).

Pitfall 2:

Returning n for all identical character strings instead of n - 1.

Crucial Edge Cases to Validate:

  • All characters identical (s = aaaa): Proper prefix cannot equal the whole string; returns n - 1 = 3.
  • No common prefix and suffix (s = abc): Returns 0.
  • Single character string (s = a): Returns 0 since proper prefix must be strictly shorter than full string.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Stress the difference between 'proper prefix' (< N) and full prefix.
  2. Explain that this exact function is the preprocessing step inside the KMP algorithm.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the fallback len = lps[len - 1] work on mismatch?

Back to DSA Sheet