forked from iiitv/algos
-
Notifications
You must be signed in to change notification settings - Fork 0
/
longest_palindromic_substring.go
46 lines (38 loc) · 962 Bytes
/
longest_palindromic_substring.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
package main
import "fmt"
// expandAroundCenter returns length of palindromic substring
func expandAroundCenter(runes []rune, left int, right int) int {
n := len(runes)
for left >= 0 && right < n && runes[left] == runes[right] {
left--
right++
}
return right - left - 1
}
// LongestPalindromicSubstring returns the longest palindromic substring in
// provided string.
// Time complexity: O(n^2)
// Space complexity: O(1)
func LongestPalindromicSubstring(str string) string {
start, end := 0, 0
runes := []rune(str)
for i := 0; i < len(runes); i++ {
a := expandAroundCenter(runes, i, i)
b := expandAroundCenter(runes, i, i+1)
length := 0
if a > b {
length = a
} else {
length = b
}
if length > end-start {
start = i - (length-1)/2
end = i + length/2
}
}
return string(runes[start : end+1])
}
func main() {
str := "And the longest palindrome is... neveroddoreven!"
fmt.Println(LongestPalindromicSubstring(str))
}