1392. Longest Happy Prefix

HardStringString MatchingHash FunctionRolling Hash
Leetcode Link

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:

  1. The solution defines a method longestPrefix within the Solution class that takes a string s as its argument.

  2. 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 using s[:-i] and s[i:], we effectively slice the string to create both the prefix and the suffix to compare.

  3. 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'.

  4. 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.

  5. 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 prefix s[:-1] is "aba" and the suffix s[1:] is "bab". They do not match.
  • In the second iteration, i = 2, the prefix s[:-2] is "ab" and the suffix s[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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Example 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.

  1. 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.
  2. 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.
  3. 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.
  4. 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".

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.


Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search can be used to find whether two components in a graph are connected.


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄