Given a string s, find the length of the longest proper prefix that is also a suffix. A proper prefix means the whole string itself is not allowed. So if s = "aaaa", the answer is 3, because "aaa" is the longest prefix that is also a suffix.
Example 1
Input: s = "ababab"
Output: 4
Explanation: The prefix "abab" and the suffix "abab" are the same, so the longest prefix-suffix length is 4.
Example 2
Input: s = "aabcdaabc"
Output: 4
Explanation: The string "aabc" appears at the beginning and at the end, so the answer is 4.
Brute Force Approach
The simplest thought is to try every possible prefix length. Since the whole string is not allowed, the largest possible proper prefix length is n - 1. For each length, compare the first length characters with the last length characters. If they match, that length is a valid prefix-suffix. By checking all possible lengths, the largest valid one can be stored as the answer. This approach is great for understanding the problem because it follows the definition directly. The only weakness is that it may compare many characters again and again.
Algorithm
Store the string length because every valid prefix-suffix length must be smaller than the full string length.
Keep an answer variable as
0. This is needed because if no non-empty prefix-suffix exists, the correct answer is0.Try every length from
1ton - 1. The upper limit keeps the prefix proper and avoids using the whole string as the answer.For each length, compare the prefix characters with the suffix characters. The suffix starts at index
n - length, so both parts have equal size.If all characters match for the current length, update the answer because a longer valid border may have been found.
Return the final answer after all possible lengths are checked.
Dry Run
Prefix Suffix in String Brute Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Finds the longest proper prefix that is also a suffix by checking every possible length. */ int longestPrefixSuffix(string s) { // Store the string length for boundary checks. int n = s.size(); // Store the best valid prefix-suffix length found so far. int answer = 0; for (int length = 1; length < n; length++) { // The suffix of this length starts from this index. int suffixStart = n - length; // Track whether the current prefix and suffix still match. bool isSame = true; for (int i = 0; i < length; i++) { // A mismatch means this length cannot be a border. if (s[i] != s[suffixStart + i]) { isSame = false; break; } } // If every character matched, this length is a valid answer. if (isSame) { answer = length; } } return answer; }};// Driver code startsint main() { string s = "ababab"; Solution obj; cout << obj.longestPrefixSuffix(s); return 0;}Complexity Analysis
Time Complexity: O(N2), because for many possible lengths, up to N characters may be compared.
Space Complexity: O(1), because only a few variables are used.
Optimal Approach
The KMP algorithm uses an array called lps, which means longest proper prefix which is also suffix. For every index i, lps[i] stores the answer for the smaller string s[0...i]. That means the last value, lps[n - 1], directly gives the longest proper prefix-suffix for the whole string.
The smart observation is this: When characters match, the current border grows by one. When characters do not match, the current border does not need to restart from zero immediately. The smaller border already known inside the previous border can be reused. This is why KMP avoids repeating comparisons.
Algorithm
Create an
lpsarray filled with0. Each index will store the best border length for the prefix ending at that index.Keep
length = 0to represent the current matched border length. This value tells which prefix character should be compared next.Start from index
1because a one-character string has no non-empty proper prefix-suffix.If
s[i]matchess[length], increaselengthand store it inlps[i]. This is done because the current border has grown by one matching character.If the characters do not match and
lengthis not zero, movelengthback tolps[length - 1]. This reuses the next smaller possible border instead of throwing away all previous work.If the characters do not match and
lengthis zero, store0at this index and move forward because no border can end here.Return
lps[n - 1], because it stores the longest proper prefix-suffix for the complete string.
Dry Run
Prefix Suffix in String Optimal Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Builds the KMP LPS array and returns the last value, which is the longest proper prefix-suffix length. */ int longestPrefixSuffix(string s) { // Store the string length for array size and loop limits. int n = s.size(); // A string of length 0 or 1 cannot have a non-empty proper border. if (n <= 1) { return 0; } // Store the best prefix-suffix length for every prefix ending index. vector<int> lps(n, 0); // Store the current matched border length. int length = 0; // Start from the second character because lps[0] is always 0. int i = 1; while (i < n) { // A match extends the current border by one character. if (s[i] == s[length]) { length++; lps[i] = length; i++; } else { // If some border exists, try the next smaller known border. if (length != 0) { length = lps[length - 1]; } else { // With no border left, this position has LPS value 0. lps[i] = 0; i++; } } } return lps[n - 1]; }};// Driver code startsint main() { string s = "aabcdaabc"; Solution obj; cout << obj.longestPrefixSuffix(s); return 0;}Complexity Analysis
Time Complexity: O(N), because each character is processed with fallback movement that never causes repeated full scans.
Space Complexity: O(N), because the LPS array stores one value for every index.
Interview follow-up Questions
A proper prefix is any prefix that is not equal to the whole string. For "abcd", "a", "ab", and "abc" are proper prefixes, but "abcd" is not.
Be the first to add a comment.