Leetcode#5

Longest Palindromic Substring

Problem statement

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

Golang solution 1

Time Complexity: O(n²)

1. Outer loop runs O(n) for all potential centers.
2. Inner expansion runs O(n) in total across all centers.
   Overall Time Complexity: O(n²)

Space complexity : O(n)

Space Complexity Analysis

1. Input String s:
   • The input string sss is already given, so it doesn’t add to the space complexity.
   • Space: O(n) (for the input string).
2. Variables:
   • maxLenPalindrome: Stores the longest palindrome substring found so far. This takes O(k) space, where k is the length of the current longest palindrome substring. In the worst case, k=n (e.g., if the input itself is a palindrome).
   • Other variables like maxLen, currentLen, and iterators (i, j) take constant space, O(1).
3. Substring Creation (inputString := s[i : j+1]):
   • In Go, string slicing (s[i:j+1]) does not create a new string but instead shares memory with the original string. This operation is O(1) in space.
   • No extra memory is allocated for inputString.
4. isPalindrome Function:
   • It uses two pointers (start, end), iterating within the bounds of the substring. These pointers require O(1) space.

Overall Space Complexity:

• The algorithm does not use any significant additional space beyond the input string and a few constant-space variables. Therefore, the space complexity is: Space Complexity: O(n)

where O(n) comes from the space required to store the input string.

Golang Code – 1

// Time Complexity  :   O(n^2)
// Space complexity :   O(n)
func longestPalindrome(s string) string {
	n := len(s)

	if n <= 1 {
		return s
	}

	maxLenPalindrome := string(s[0])
	maxLen := 0

	// we are using two for loop
	// to get all variation of substring from input string
	for i := 0; i < n; i++ {
		for j := i; j < n; j++ {

			currentLen := j - i + 1
			if i != j && currentLen > maxLen {
				if isPalindrome(s, i, j) {
					// we need to include jth letter as well
					maxLenPalindrome = s[i : j+1]
					maxLen = currentLen
				}
			}
		}
	}

	return maxLenPalindrome
}

func isPalindrome(s string, start, end int) bool {
	for i := start; i < end; i, end = i+1, end-1 {
		if s[i] != s[end] {
			return false
		}
	}

	return true
}

Golang solution 2

Manacher’s Algorithm to find the longest palindromic substring

Explanation:

1. Preprocessing:
   • Adds separators (#) between characters and special boundaries (^ at the start, $ at the end).
   • Example: For s = "babad", transformed string is t = "^#b#a#b#a#d#$".
2. Palindrome Array (p):
   • p[i] stores the radius of the palindrome centered at index i in the transformed string.
3. Expansion:
   • For each index i, try to expand the palindrome centered at i as far as possible.
4. Center and Boundary Update:
   • When a palindrome extends beyond the current boundary, update the center (c) and right boundary (r).
5. Result Extraction:
   • After processing, find the maximum value in p to determine the length and position of the longest palindrome in the original string.

Example Run:

Input: "babad"

1. Transformed string: "^#b#a#b#a#d#$"
2. Palindrome radius array p: [0, 0, 1, 0, 3, 0, 1, 0, 1, 0, 0]
3. Longest palindrome: "bab" (or "aba" depending on the center position).

// Time Complexity  :   O(n)
// Space complexity :   O(n)

func longestPalindrome(s string) string {
	// Transform the string by adding separators (#) and boundaries (^ and $)
	t := preprocess(s)
	n := len(t)
	p := make([]int, n) // Array to store palindrome radii

	// Current center and right boundary of the rightmost palindrome
	currentCenter, rightBoundary := 0, 0

	// Find palindromes in the transformed string
	for i := 1; i < n-1; i++ {
		// Mirror index of i around the center c
		mirror := 2*currentCenter - i

		// Initialize p[i] based on its mirror or the right boundary
		if i < rightBoundary {
			p[i] = min(rightBoundary-i, p[mirror])
		}

		// Expand around the current center i
		for t[i+1+p[i]] == t[i-1-p[i]] {
			p[i]++
		}

		// Update the center and right boundary if the palindrome at i extends beyond r
		if i+p[i] > rightBoundary {
			currentCenter = i
			rightBoundary = i + p[i]
		}
	}

	// Find the maximum length palindrome in the transformed string
	maxLen := 0
	centerIndex := 0
	for i := 1; i < n-1; i++ {
		if p[i] > maxLen {
			maxLen = p[i]
			centerIndex = i
		}
	}

	// Map the center and length back to the original string
	// Map from transformed string index
	start := (centerIndex - maxLen) / 2
	return s[start : start+maxLen]
}

// Helper function to preprocess the string
func preprocess(s string) string {
	if len(s) == 0 {
		return "^$"
	}
	t := "^"
	for _, char := range s {
		t += "#" + string(char)
	}
	t += "#$"
	return t
}

// Helper function to find the minimum of two integers
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

Time complexity : O(n)

Space complexity : O(n)