Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1392.html
1392. Longest Happy Prefix (Hard)
A string is called a happy prefix if is a non-empty prefix which is also a suffix (excluding itself).
Given a string s
. Return the longest happy prefix of s
.
Return an empty string if no such prefix exists.
Example 1:
Input: s = "level" Output: "l" Explanation: s contains 4 prefix excluding itself ("l", "le", "lev", "leve"), and suffix ("l", "el", "vel", "evel"). The largest prefix which is also suffix is given by "l".
Example 2:
Input: s = "ababab" Output: "abab" Explanation: "abab" is the largest prefix which is also suffix. They can overlap in the original string.
Example 3:
Input: s = "leetcodeleet" Output: "leet"
Example 4:
Input: s = "a" Output: ""
Constraints:
1 <= s.length <= 10^5
s
contains only lowercase English letters.
Related Topics:
String
Solution 1. Brute Force with string_view
// OJ: https://leetcode.com/problems/longest-happy-prefix/
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
string longestPrefix(string s) {
int n = s.size();
string_view sv = s;
for(int len = n-1; len>=1; len--){
if (sv.substr(0, len) == sv.substr(n-len))
return s.substr(0, len);
}
return "";
}
};
Solution 2. Rolling Hash
// OJ: https://leetcode.com/problems/longest-happy-prefix/
// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/longest-happy-prefix/discuss/547446/C%2B%2BJava-with-picture-incremental-hash-and-DP
class Solution {
typedef unsigned long long ULL;
public:
string longestPrefix(string s) {
ULL N = s.size(), len = 0, mod = 1e9+7, L = 0 , R = 0, mul = 1;
for (int i = 0; i < N - 1; ++i) {
L = (L * 26 + s[i] - 'a') % mod;
R = (R + mul * (s[N - 1 - i] - 'a')) % mod;
if (L == R) len = i + 1;
mul = mul * 26 % mod;
}
return s.substr(0, len);
}
};
Java
-
class Solution { public String longestPrefix(String s) { if (s == null) return s; int length = s.length(); if (length <= 1) return ""; int[] prefix = prefix(s); return s.substring(0, prefix[length - 1] + 1); } public int[] prefix(String str) { int length = str.length(); int[] prefix = new int[length]; Arrays.fill(prefix, -1); int index = -1; for (int i = 1; i < length; i++) { while (index >= 0 && str.charAt(index + 1) != str.charAt(i)) index = prefix[index]; if (str.charAt(index + 1) == str.charAt(i)) index++; prefix[i] = index; } return prefix; } }
-
// OJ: https://leetcode.com/problems/longest-happy-prefix/ // Time: O(N^2) // Space: O(1) class Solution { public: string longestPrefix(string s) { int n = s.size(); string_view sv = s; for(int len = n-1; len>=1; len--){ if (sv.substr(0, len) == sv.substr(n-len)) return s.substr(0, len); } return ""; } };
-
class Solution: def longestPrefix(self, s: str) -> str: for i in range(1, len(s)): if s[:-i] == s[i:]: return s[i:] return ''