Palindrome Partitioning Using Backtracking in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if a substring is a palindrome.

DSA Go

func isPalindrome(s string, left int, right int) bool {
    for left < right {
        if s[left] != s[1] {
            return false
        }
        left++
        right--
    }
    return true
}

Drag options to blanks, or click blank then click option'

A[right]

B(right)

C{right}

D<right>

Attempts:

3 left

💡 Hint

Common Mistakes

Using parentheses or braces instead of square brackets for indexing.

Confusing the order of left and right indices.

We use s[left] and s[right] to compare characters at positions left and right. The correct syntax for indexing a string in Go is s[index] with square brackets.

2fill in blank

medium

Complete the code to append a substring to the current partition.

DSA Go

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; end < len(s); end++ {
        if isPalindrome(s, start, end) {
            path = append(path, s[1])
            backtrack(s, end+1, path, result)
            path = path[:len(path)-1]
        }
    }
}

Drag options to blanks, or click blank then click option'

A<start:end+1>

B(start:end+1)

C{start:end+1}

D[start:end+1]

Attempts:

3 left

💡 Hint

Common Mistakes

Using parentheses or braces instead of square brackets for slicing.

Not adding 1 to the end index, missing the last character.

In Go, slicing a string uses square brackets with start and end indices: s[start:end]. To include the character at end, we use end+1.

3fill in blank

hard

Fix the error in the backtracking function call to correctly pass the result pointer.

DSA Go

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

Drag options to blanks, or click blank then click option'

Aresult

B&result

C*result

Dresult[]

Attempts:

3 left

💡 Hint

Common Mistakes

Passing the slice by value, which prevents the function from modifying the original result.

Using *result which is invalid here because result is not a pointer.

The backtrack function expects a pointer to the result slice, so we pass &result to allow modifications inside the function.

4fill in blank

hard

Fill both blanks to complete the palindrome partitioning backtracking loop.

DSA Go

for end := [1]; end < [2]; end++ {
    if isPalindrome(s, start, end) {
        path = append(path, s[start:end+1])
        backtrack(s, end+1, path, result)
        path = path[:len(path)-1]
    }
}

Drag options to blanks, or click blank then click option'

Astart

Blen(s)

C0

Dlen(path)

Attempts:

3 left

💡 Hint

Common Mistakes

Starting loop from 0 instead of start.

Using len(path) instead of len(s) for loop limit.

The loop starts from 'start' index and goes until the length of the string 'len(s)' to check all possible substrings.

5fill in blank

hard

Fill all three blanks to complete the partition function with backtracking.

DSA Go

func partition(s string) [][]string {
    var result [][]string
    backtrack(s, [1], [2], [3])
    return result
}

Drag options to blanks, or click blank then click option'

A0

B[]string{}

C&result

Dnil

Attempts:

3 left

💡 Hint

Common Mistakes

Passing nil instead of an empty slice for path.

Not passing the pointer to result.

Starting from an index other than 0.

We start from index 0, use an empty slice for the current path, and pass the address of result to collect partitions.

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"