Find all palindromes in a string in Go

For this post, we're going to play with palindromes again but with a different technique.

Write a golang function that finds all palindromes in a string.

For this problem, we employ the 'expand from center' technique for determining if the string is a palindrome. This algorithm uses dual pointers that will move from the center of a candidate string, one moving left the other moving right. As long as the characters at those pointers remain the same, we have identified a palindrome.

func expand(i int, j int, str string, palindromes map[string]string) map[string]string {
    runes := []rune(str)
    for i >= 0 && j < len(str) && runes[i] == runes[j] {
        pal := string(runes[i : j+1])
        palindromes[pal] = pal
        i -= 1
        j += 1
    }
    return palindromes
}

Imagine that i and j start are both 0, we have a string of length 1, i and j point to the same character, so we have a 1 character palindrome.

Now suppose the string is 3 letters, 'aba', and i and j are both 1. the expand function will find 'b' as a palindrome, move i and j 1 step to 0 and 2, respectively. The characters pointed to by i and j are equal, so we have a second palindrome, 'aba'.

To implement the scan, we simply set up a loopto sweep across the string. Due to the odd indexing scheme, it is necessary to sweep for odd length and even length palindromes separately.

The palindromes are stored in a map for easy deduplication.

func FindAllPalindromes(str string) []string {
    palindromes := map[string]string{}

    for i := 0; i < len(str); i++ {
        palindromes = expand(i, i, str, palindromes)
    }
    for i := 0; i < len(str)-1; i++ {
        palindromes = expand(i, i+1, str, palindromes)
    }
    //fmt.Printf("palindromes: %+v", palindromes)
    res := []string{}
    for _, v := range palindromes {
        res = append(res, v)
    }
    return res
}

It turns out, the unit test has a curveball worth noting here.

The FindAllPalindromes function builds the result array in whatever order the map iterates them. This may or may not be the order of the 'expected' result in the unit test.
For example, the string, 'aba', has 3 palindromes: 'a', 'aba', and 'b'. However, FindAllPalindromes returns 'aba', 'a', and 'b'.

We have several options here:

• write a function that compares two arrays without regard to order, ie the 2 arrays have the same elements and length.

• sort both the expected and result arrays, then compare

For simplicity, I chose the second option but have built the expected result of the test cases in presorted form to squeeze a little time off test runs.

func TestFindAllPalindromes(t *testing.T) {
    testCases := []struct {
        input    string
        expected []string
    }{
        // note that expected arrays have been presorted for quicker test runs
        {"", []string{}},
        {"a", []string{"a"}},
        {"ab", []string{"a", "b"}},
        {"aba", []string{"a", "aba", "b"}},
        {"aab", []string{"a", "aa", "b"}},
        {"abcba", []string{"a", "abcba", "b", "bcb", "c"}},
    }

    for _, tc := range testCases {
        results := FindAllPalindromes(tc.input)
        // sort result to match expected order
        slices.Sort(results)
        if !reflect.DeepEqual(results, tc.expected) {
            t.Errorf("findUniqueCombinations(%q) = %v; expected %v", tc.input, results, tc.expected)
        }
    }
}

How can we make this better?

Post your thoughts in the comments.

Thanks!

The code for this post and all posts in this series can be found here