1392. Longest Happy Prefix
Problem Description
The problem presents a string processing task where we need to find the longest possible substring that serves two roles simultaneously: it is a prefix and a suffix of the given string s
. A prefix is a start part of the string, and a suffix is an ending part of the string. It's important to note however that the 'happy prefix' we are looking for cannot be the entire string itself, it should be strictly non-empty and shorter than the full string.
Intuition
The intuition behind the solution is fairly straightforward. We want to find the longest sequence at the beginning of the string (s
) that is repeated at the end. The naive approach would be to consider each possible prefix of the string and check if it's also a suffix.
To implement this, we can start checking the longest possible prefix/suffix first and narrow down to the shorter ones. This is done by slicing the string: for a prefix starting from the beginning of the string s
and ending at s[:-i]
, check if there's an equivalent suffix starting at s[i:]
and going to the end of the string. If such a match is found, then s[i:]
is our longest 'happy prefix'. If no match is found all the way up to the shortest prefix (a single character), return an empty string.
The solution starts the loop from 1 (as opposed to starting from 0) because we want a non-empty prefix/suffix. Additionally, we loop until len(s)
because s[:-len(s)]
would give us an empty string which is not a valid 'happy prefix', and we're looking for a prefix/suffix pair that does not include the entire string itself.
Solution Approach
The provided solution uses a straightforward brute-force approach. There's no need for complex algorithms or additional data structures. The approach is based on string comparison and slicing only.
Here's a step-by-step explanation of the implemented solution:
-
The solution defines a method
longestPrefix
within theSolution
class that takes a strings
as its argument. -
The method initiates a loop that starts at 1 and ends just before the length of the string. The loop iterates with
i
indicating the current size of the suffix and prefix that are being compared. By usings[:-i]
ands[i:]
, we effectively slice the string to create both the prefix and the suffix to compare. -
At each iteration, the algorithm checks whether the current prefix (
s[:-i]
) is equal to the current suffix (s[i:]
). If these two substrings are the same, it means we have found a 'happy prefix'. -
The loop starts checking from the longest possible happy prefix and goes down to the shortest. The reasoning behind this order is that we are interested in the longest happy prefix. If a match is found, it will be the longest one due to the order of the loop, and the method can return immediately without checking the rest.
-
If no 'happy prefix' is found throughout the loop, the method returns an empty string
''
, indicating that no such prefix exists for the given string.
To visualize, let's consider s = "abab"
as an example:
- In the first iteration,
i = 1
, the prefixs[:-1]
is "aba" and the suffixs[1:]
is "bab". They do not match. - In the second iteration,
i = 2
, the prefixs[:-2]
is "ab" and the suffixs[2:]
is "ab". They match, so "ab" is returned as the longest happy prefix.
This solution approach has a time complexity of O(n^2), where n is the length of the string, due to the fact that string comparison is done in each iteration over slices of the string that decrease in size by one character each time.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example using the string s = "level"
to illustrate the solution approach. We are looking for the longest substring that is both a prefix and a suffix of s
but is not s
itself.
-
Iteration 1:
i = 1
- Prefix:
s[:-1]
is "leve" - Suffix:
s[1:]
is "evel" - Comparison: "leve" is not equal to "evel", so we continue to the next iteration.
- Prefix:
-
Iteration 2:
i = 2
- Prefix:
s[:-2]
is "lev" - Suffix:
s[2:]
is "vel" - Comparison: "lev" is not equal to "vel", so we continue to the next iteration.
- Prefix:
-
Iteration 3:
i = 3
- Prefix:
s[:-3]
is "le" - Suffix:
s[3:]
is "el" - Comparison: "le" is not equal to "el", so we continue to the next iteration.
- Prefix:
-
Iteration 4:
i = 4
- Prefix:
s[:-4]
is "l" - Suffix:
s[4:]
is "l" - Comparison: "l" is equal to "l"
- Since we have found that the prefix is equal to the suffix, "l" is the longest "happy prefix".
- Prefix:
In this case, since "l" is the longest substring that meets the criteria, the method returns "l". If no matching substrings had been found, the method would return an empty string ''
.
The solution is efficient because it uses a loop to progressively shorten the prefixes and suffixes from the longest to the shortest, stopping early when a match is found, which is more optimal compared to checking in the opposite direction. Additionally, by not using additional data structures, the approach keeps memory usage minimal.
Solution Implementation
1class Solution:
2 def longest_prefix(self, s: str) -> str:
3 # Initialize the maximum length of the longest prefix that is also a suffix
4 max_prefix_length = 0
5
6 # Start checking for prefixes and suffixes from the shortest length towards the longest
7 for i in range(1, len(s)):
8 # Check if the prefix is equal to the suffix
9 # We slice the string s from the beginning to the end minus i (prefix)
10 # And compare it to the substring from i to the end (suffix)
11 if s[:-i] == s[i:]:
12 # If they are equal, we update the maximum length of the prefix
13 max_prefix_length = len(s) - i
14
15 # Return the longest prefix that is also a suffix
16 # We slice the string s to the length of the maximum prefix found
17 return s[:max_prefix_length]
18
19# Example of usage:
20# solution = Solution()
21# print(solution.longest_prefix("level")) # Output: "l"
22
1class Solution {
2 // Arrays to store the precomputed hash values and powers of the base
3 private long[] power;
4 private long[] hash;
5
6 /**
7 * Function to find the longest prefix which is also a suffix.
8 *
9 * @param s the input string
10 * @return the longest prefix which is also a suffix without overlapping
11 */
12 public String longestPrefix(String s) {
13 int base = 131; // A prime number used as the base for hashing
14 int n = s.length();
15 power = new long[n + 10]; // Expanded size to prevent array index out of bounds
16 hash = new long[n + 10];
17 power[0] = 1; // Initializing the first element of power to 1
18
19 // Precompute the powers and hash values for the input string
20 for (int i = 0; i < n; ++i) {
21 power[i + 1] = power[i] * base;
22 hash[i + 1] = hash[i] * base + s.charAt(i);
23 }
24
25 // Iterate from longest possible prefix to the shortest
26 for (int length = n - 1; length > 0; --length) {
27 // If the prefix hash and suffix hash matches, return the prefix
28 if (getHash(1, length) == getHash(n - length + 1, n)) {
29 return s.substring(0, length);
30 }
31 }
32
33 // No prefix matches the suffix, return an empty string
34 return "";
35 }
36
37 /**
38 * Helper function to get the hash of a substring.
39 *
40 * @param left left index of the substring (inclusive, 1-indexed)
41 * @param right right index of the substring (inclusive, 1-indexed)
42 * @return the hash value of the substring
43 */
44 private long getHash(int left, int right) {
45 // Compute the substring's hash by subtracting the hash before the substring
46 // and adjusting with the power to avoid hash collision
47 return hash[right] - hash[left - 1] * power[right - left + 1];
48 }
49}
50
1#include <string>
2using std::string;
3
4typedef unsigned long long ull;
5
6class Solution {
7public:
8 // Calculate the longest prefix which is also a suffix
9 string longestPrefix(string s) {
10 int base = 131; // The base for the polynomial hash
11 int n = s.size(); // Length of the string
12 ull power[n + 10]; // Stores the powers of base, power[i] = base^i
13 ull hash[n + 10]; // Stores the hash values for the prefix ending at each index
14
15 // Initializing the power and hash arrays
16 power[0] = 1;
17 hash[0] = 0;
18
19 // Populate power and hash arrays
20 for (int i = 0; i < n; ++i) {
21 power[i + 1] = power[i] * base;
22 hash[i + 1] = hash[i] * base + s[i];
23 }
24
25 // Iterate from the end and check if a prefix is also a suffix
26 for (int length = n - 1; length > 0; --length) {
27 ull prefixHash = hash[length]; // Hash value of the current prefix
28 ull suffixHash = hash[n] - hash[n - length] * power[length]; // Hash value of the current suffix
29
30 // If the computed prefix and suffix hash values are equal, we've found the longest prefix-suffix
31 if (prefixHash == suffixHash) {
32 return s.substr(0, length);
33 }
34 }
35
36 // If no proper prefix-suffix pair is found, return an empty string
37 return "";
38 }
39};
40
1/**
2 * Finds the longest prefix which is also a suffix of the string.
3 * The prefix must be non-empty and less than the string length.
4 *
5 * @param {string} str - The string to analyze.
6 * @returns {string} The longest prefix which is also a suffix.
7 */
8function longestPrefix(str: string): string {
9 // Get the length of the string
10 const lengthOfString: number = str.length;
11
12 // Iterate backwards from the end of the string
13 for (let i = lengthOfString - 1; i >= 0; i--) {
14 // Compare substring from start to the current index (prefix)
15 // with substring from the end of the string with the same length (suffix)
16 if (str.slice(0, i) === str.slice(lengthOfString - i)) {
17 // If they are equal, return the prefix as the longest prefix which is also a suffix
18 return str.slice(0, i);
19 }
20 }
21
22 // No prefix which is also suffix was found, return empty string
23 return '';
24}
25
Time and Space Complexity
Time Complexity
The provided code snippet calculates the longest prefix of a given string s
that is also a suffix by checking each substring. The outer for loop runs (len(s) - 1)
times. For each iteration of the loop, the slicing operation [i:]
and [:-i]
has a time complexity of O(n)
, where n
is the length of the string. Since the slicing happens twice for each iteration and the comparison also takes O(n)
for each iteration, the total time complexity is:
O((n - 1) * 2n)
= O(2n^2 - 2n)
which simplifies to O(n^2)
.
Therefore, the time complexity of the code is O(n^2)
.
Space Complexity
Since the algorithm only uses a constant amount of extra space for variables like i
and the space needed for storing the prefixes/suffixes which are being compared is also not additional as they are references to existing substrings in s
, the space complexity is O(1)
. There is no additional space being used that grows with the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
How does quick sort divide the problem into subproblems?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!