Palindromic Substrings

1. Problem Description

Given a string, calculate how many palindromic substrings it contains.

Substrings with different starting or ending positions are considered different even if they consist of the same characters.

2. Approach

• Brute force
• Center expansion

3. Implementation

3.1. Brute Force

• Recursion

// Recursion
func countSubstrings(s string) int {
	count := 0

	countSubstringsDFS(s, 0, &count)

	return count
}

func countSubstringsDFS(s string, length int, count *int) {
	if length > len(s) {
		return
	}

	for i := 0; i < len(s)-length; i++ {
		if isHuiWen(s, i, i+length) {
			*count++
		}
	}

	countSubstringsDFS(s, length+1, count)
}

• Loop

// Loop
func countSubstrings2(s string) int {
	count := 0

	for i := 0; i < len(s); i++ {
		for j := 0; j < len(s)-i; j++ {
			if isHuiWen(s, j, j+i) {
				count++
			}
		}
	}

	return count
}

3.2. Center Expansion

func countSubstrings(s string) int {
    chars := []rune(s)
    res := 0
    for i, _ := range chars {
        res += spread(chars, i,i)
        res += spread(chars, i,i+1)
    }
    return res
}

func spread(chars []rune, left ,right int) int {
    count := 0
    for left >= 0 && right <= len(chars)-1 {
        if chars[left] == chars[right] {
            count++
            left--
            right++
        }else {
            break
        }
    }
    return count
}

4. References

• 647. Palindromic Substrings - LeetCode