Problem Statement
Given a string S, we have to return the Longest Happy Prefix of S. String S will be a Happy Prefix if it is a non-empty prefix which is also a suffix (excluding itself). In case there exists no Happy Prefix, simply return an empty string.
Example 1:
Input: S = "madam"
Output: "m"
Explanation: Prefixes of S are ("m", "ma", "mad", "mada") and suffixes are ("m", "am", "dam", "adam"). Hence the longest prefix that is the suffix also is "m".
Example 2:
Input: S = "pastaisreadypasta"
Output: "pasta"
Explanation:
Example 3:
Input: S = "t"
Output: ""
Explanation: String has only 1 character, hence no suffix is possible.
Constraints:
- 1 <= S.length <= 10^5
- S contains only lowercase English letters ('a'-'z')
Solutions
Solution 1 : Brute Force Approach with O(N^2) complexity
def longestHappyPrefix(S):
result = ""
for j in range(1, len(S)):
prefix = S[:j]
suffix = S[-j:]
if prefix == suffix and len(prefix) > len(result):
result = prefix
return result
# Driver code
if __name__ == "__main__":
S = 'madam'
print(longestHappyPrefix(S))
def longestHappyPrefix(S):
for j in range(1, len(S)):
if S.startswith(S[j:]):
return S[j:]
return ""
# Driver code
if __name__ == "__main__":
S = 'madam'
print(longestHappyPrefix(S))
Solution 3: Simple solution in O(N) complexity
def longestHappyPrefix(S):
a = len(S)
for i in range(a-2,-1,-1):
if(S[:i+1] == S[a-i-1:]):
return S[:i+1]
return ""
# Driver code
if __name__ == "__main__":
S = 'madam'
print(longestHappyPrefix(S))
Solution 4 : Using Knuth-Morris-Pratt (KMP) Algorithm with O(N) complexity
def longestHappyPrefix(S):
if not S:
return ""
prefix = S
left, right, pattern = 0, 1, [None] * len(prefix)
while right < len(prefix):
if prefix[left] == prefix[right]:
pattern[right] = left
left, right = left + 1, right + 1
elif left > 0 and pattern[left - 1] is not None:
left = pattern[left - 1] + 1
elif left > 0:
left = 0
else:
right += 1
result = pattern[-1] + 1 if pattern[-1] is not None else 0
return S[:result]
# Driver code
if __name__ == "__main__":
S = 'madam'
print(longestHappyPrefix(S))
You can read more about KMP Algorithm here.
Solution 5 : Using Rabin - Karp | Rolling - Hash Method with O(N) complexity
def longestHappyPrefix(S):
a = len(S)
left = 0
right = 0
pattern = 1
prime = 10 ** 9 + 7
result = 0
for j in range(a - 1):
left = (left * 128 + ord(S[j])) % prime
right = (right + pattern * ord(S[a - j - 1])) % prime
if left == right:
result = j + 1
pattern = (pattern * 128) % prime
return S[:result]
if __name__ == "__main__":
S = 'madam'
print(longestHappyPrefix(S))
Comments
Post a Comment