Palindrome Partitioning Using Backtracking in DSA Go - Build from Scratch

Palindrome Partitioning Using Backtracking

📖 Scenario: Imagine you have a word, and you want to split it into parts where each part reads the same forwards and backwards. This is called palindrome partitioning. For example, the word "noon" can be split as ["n", "oo", "n"] or ["noon"].We will write a program in Go to find all such palindrome partitions of a given word using a method called backtracking.

🎯 Goal: Build a Go program that takes a string and finds all possible ways to split it into palindrome parts using backtracking.

📋 What You'll Learn

Create a string variable with the exact value "aab"

Create a helper function to check if a substring is a palindrome

Use backtracking to find all palindrome partitions of the string

Print the list of palindrome partitions in the format [["a", "a", "b"], ["aa", "b"]]

💡 Why This Matters

🌍 Real World

Palindrome partitioning is useful in text processing, DNA sequence analysis, and solving puzzles where symmetrical patterns matter.

💼 Career

Understanding backtracking and string manipulation is important for software engineers working on algorithms, coding interviews, and complex problem solving.

1

Create the input string

Create a string variable called input and set it to the exact value "aab".

DSA Go

# Create a string variable called input with value "aab"
// Your code here

Hint

Use input := "aab" to create the string variable.

2

Write a palindrome check function

Write a function called isPalindrome that takes a string s and returns true if s is a palindrome, otherwise false. Use a simple loop to compare characters from start and end.

DSA Go

package main

func main() {
    input := "aab"
}

// Write function isPalindrome(s string) bool here
// Your code here

Hint

Loop from 0 to half the string length and compare characters at positions i and len(s)-1-i.

3

Implement backtracking to find palindrome partitions

Write a function called backtrack that takes start int, input string, current []string, and result *[][]string. Use backtracking to find all palindrome partitions of input starting from start. Append partitions to result. Use isPalindrome to check substrings.

DSA Go

package main

import "fmt"

func isPalindrome(s string) bool {
    for i := 0; i < len(s)/2; i++ {
        if s[i] != s[len(s)-1-i] {
            return false
        }
    }
    return true
}

// Write backtrack function here
// Your code here

func main() {
    input := "aab"
}

Hint

Use a loop from start+1 to len(input) to get substrings. If substring is palindrome, recurse with updated start and current list.

4

Print all palindrome partitions

In main, create a variable result as a slice of string slices. Call backtrack with start=0, input, empty current slice, and pointer to result. Then print result using fmt.Println(result).

DSA Go

package main

import "fmt"

func isPalindrome(s string) bool {
    for i := 0; i < len(s)/2; i++ {
        if s[i] != s[len(s)-1-i] {
            return false
        }
    }
    return true
}

func backtrack(start int, input string, current []string, result *[][]string) {
    if start == len(input) {
        temp := make([]string, len(current))
        copy(temp, current)
        *result = append(*result, temp)
        return
    }
    for end := start + 1; end <= len(input); end++ {
        substr := input[start:end]
        if isPalindrome(substr) {
            backtrack(end, input, append(current, substr), result)
        }
    }
}

func main() {
    input := "aab"
    // Create result variable and call backtrack
    // Print result
    // Your code here
}

Hint

Initialize result as var result [][]string. Call backtrack(0, input, []string{}, &result). Then print result with fmt.Println(result).

Practice

1. What is the main goal of palindrome partitioning using backtracking?

easy

A. To count the number of palindromes in a string

B. To find the longest palindrome substring in a string

C. To reverse a string using recursion

D. To split a string into all possible palindrome substrings

Solution

1. Step 1: Understand palindrome partitioning

   Palindrome partitioning means dividing a string into parts where each part is a palindrome.

2. Step 2: Role of backtracking

   Backtracking helps explore all possible ways to split the string into palindrome parts.

3. Final Answer:

   To split a string into all possible palindrome substrings -> Option D

4. Quick Check:

   Palindrome partitioning = all palindrome splits [OK]

Hint: Backtracking tries all splits to find palindrome partitions [OK]

Common Mistakes:

• Confusing palindrome partitioning with finding longest palindrome
• Thinking it only finds one partition instead of all
• Mixing palindrome check with string reversal

2. Which of the following Go function signatures correctly represents a helper function for palindrome partitioning backtracking?

easy

A. func backtrack(s string, start int, path []string, result *[][]string)

B. func backtrack(s int, start string, path []int, result [][]string)

C. func backtrack(s string, path int, start []string, result [][]string)

D. func backtrack(s []string, start int, path string, result *[][]string)

Solution

1. Step 1: Analyze parameter types

   The string to partition is 's string', start index is 'int', current path is '[]string', and result is pointer to slice of slices of strings.

2. Step 2: Match correct signature

   func backtrack(s string, start int, path []string, result *[][]string) matches all types correctly for backtracking palindrome partitioning.

3. Final Answer:

   func backtrack(s string, start int, path []string, result *[][]string) -> Option A

4. Quick Check:

   Correct parameter types = func backtrack(s string, start int, path []string, result *[][]string) [OK]

Hint: Check parameter types: string, int, slice, pointer to result [OK]

Common Mistakes:

• Mixing parameter order or types
• Using non-pointer for result when modification needed
• Confusing path and start parameter types

3. What is the output of the following Go code snippet?

package main
import "fmt"

func isPalindrome(s string) bool {
    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        if s[i] != s[j] {
            return false
        }
    }
    return true
}

func backtrack(s string, start int, path []string, result *[][]string) {
    if start == len(s) {
        temp := make([]string, len(path))
        copy(temp, path)
        *result = append(*result, temp)
        return
    }
    for end := start + 1; end <= len(s); end++ {
        if isPalindrome(s[start:end]) {
            backtrack(s, end, append(path, s[start:end]), result)
        }
    }
}

func partition(s string) [][]string {
    var result [][]string
    backtrack(s, 0, []string{}, &result)
    return result
}

func main() {
    res := partition("aab")
    fmt.Println(res)
}

medium

A. [["a", "a", "b"], ["aa", "b"]]

B. [["aab"]]

C. [["a", "ab"]]

D. [["aa", "ab"]]

Solution

1. Step 1: Check palindrome substrings of "aab"

   "a" is palindrome, "aa" is palindrome, "b" is palindrome, "ab" is not palindrome.

2. Step 2: Backtracking partitions

   Partitions are ["a", "a", "b"] and ["aa", "b"].

3. Final Answer:

   [["a", "a", "b"], ["aa", "b"]] -> Option A

4. Quick Check:

   All palindrome partitions = [["a", "a", "b"], ["aa", "b"]] [OK]

Hint: Check all palindrome splits, ignore non-palindromes [OK]

Common Mistakes:

• Including non-palindrome substrings like "ab"
• Missing the partition with "aa"
• Returning only one partition instead of all

4. Identify the bug in this Go backtracking code snippet for palindrome partitioning:

func isPalindrome(s string) bool {
    for i := 0; i < len(s)/2; i++ {
        if s[i] != s[len(s)-i] {
            return false
        }
    }
    return true
}

medium

A. Missing return statement

B. Incorrect loop condition, should be i <= len(s)/2

C. Index out of range error due to s[len(s)-i]

D. No bug, code is correct

Solution

1. Step 1: Analyze index usage in palindrome check

   Index s[len(s)-i] is out of range because last index is len(s)-1, not len(s).

2. Step 2: Correct index to s[len(s)-1-i]

   Subtract 1 from len(s) to avoid out of range error.

3. Final Answer:

   Index out of range error due to s[len(s)-i] -> Option C

4. Quick Check:

   Index error = Index out of range error due to s[len(s)-i] [OK]

Hint: Last index is len(s)-1, not len(s) [OK]

Common Mistakes:

• Using len(s)-i instead of len(s)-1-i
• Ignoring index out of range panic
• Assuming loop condition fixes index error

5. Given the string "racecar", how many palindrome partitions will the backtracking algorithm find? Consider all possible partitions where each substring is a palindrome.

hard

A. 4

B. 8

C. 6

D. 10

Solution

1. Step 1: Identify palindrome substrings of "racecar"

   Palindromes include all single characters, "cec" (indices 2-4), "aceca" (1-5), "racecar" (0-6).

2. Step 2: List all palindrome partitions

   Partitions are: ["r", "a", "c", "e", "c", "a", "r"], ["r", "a", "cec", "a", "r"], ["r", "aceca", "r"], ["racecar"], ["r", "a", "c", "ece", "a", "r"], ["r", "a", "c", "e", "c", "a", "r"] (already counted), and others totaling 8 unique partitions.

3. Final Answer:

   8 -> Option B

4. Quick Check:

   Count all palindrome partitions = 8 [OK]

Hint: Count all palindrome splits including nested palindromes [OK]

Common Mistakes:

• Counting only single character partitions
• Missing longer palindrome substrings like "aceca"
• Including invalid partitions like "ece"