Palindrome Partitioning Using Backtracking in DSA Javascript - Build from Scratch

Palindrome Partitioning Using Backtracking

📖 Scenario: You are building a tool that splits a word into parts where each part is a palindrome. This helps in word games and text analysis.

🎯 Goal: Create a program that finds all ways to split a given string so that every piece is a palindrome.

📋 What You'll Learn

Create a string variable called inputString with the value "aab".

Create a helper function called isPalindrome that checks if a string is a palindrome.

Use backtracking in a function called partition to find all palindrome partitions of inputString.

Print the result array of palindrome partitions.

💡 Why This Matters

🌍 Real World

Palindrome partitioning helps in text analysis, DNA sequence studies, and word games where palindromic patterns are important.

💼 Career

Understanding backtracking and string manipulation is useful for software developers working on algorithms, coding interviews, and problem-solving tasks.

1

Create the input string

Create a string variable called inputString and set it to "aab".

DSA Javascript

// Create the input string variable
// Your code here

Hint

Use const inputString = "aab"; to create the string.

2

Write the palindrome checker function

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

DSA Javascript

const inputString = "aab";

// Write the isPalindrome function below
// Your code here

Hint

Check characters from start and end moving towards the center.

3

Implement the backtracking partition function

Create a function called partition that takes a string s and returns an array of arrays with all palindrome partitions. Use a helper function inside called backtrack with parameters start and path. Use isPalindrome to check substrings. Use a for loop with variable end from start to s.length - 1. If substring s.slice(start, end + 1) is palindrome, add it to path, recurse with end + 1, then remove last element from path.

DSA Javascript

const inputString = "aab";

function isPalindrome(s) {
    for (let i = 0; i < s.length / 2; i++) {
        if (s[i] !== s[s.length - 1 - i]) {
            return false;
        }
    }
    return true;
}

// Write the partition function below
// Your code here

Hint

Use backtracking to explore all substring partitions and check palindromes.

4

Print the palindrome partitions

Call the partition function with inputString and print the result using console.log.

DSA Javascript

const inputString = "aab";

function isPalindrome(s) {
    for (let i = 0; i < s.length / 2; i++) {
        if (s[i] !== s[s.length - 1 - i]) {
            return false;
        }
    }
    return true;
}

function partition(s) {
    const result = [];
    function backtrack(start, path) {
        if (start === s.length) {
            result.push([...path]);
            return;
        }
        for (let end = start; end < s.length; end++) {
            const substring = s.slice(start, end + 1);
            if (isPalindrome(substring)) {
                path.push(substring);
                backtrack(end + 1, path);
                path.pop();
            }
        }
    }
    backtrack(0, []);
    return result;
}

// Print the palindrome partitions
// Your code here

Hint

Use console.log(partition(inputString)); to print the result.

Practice

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

easy

A. To split a string into all possible palindrome substrings

B. To find the longest palindrome substring in a string

C. To reverse a string using recursion

D. To count the number of palindromes in a string

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 and keep only palindrome parts.

3. Final Answer:

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

4. Quick Check:

   Palindrome partitioning = splitting into palindrome substrings [OK]

Hint: Backtracking tries all splits keeping palindromes only [OK]

Common Mistakes:

• Confusing palindrome partitioning with longest palindrome substring
• Thinking it only finds one palindrome partition
• Assuming it reverses the string

2. Which of the following is the correct way to check if a substring s.slice(start, end) is a palindrome in JavaScript?

easy

A. Check if s.slice(start, end) === s.slice(end, start).reverse()

B. Check if s.slice(start, end) === s.slice(start, end).split('').reverse().join('')

C. Check if s.slice(start, end) === s.reverse()

D. Check if s.slice(start, end) === s.split('').reverse()

Solution

1. Step 1: Extract substring correctly

   Use s.slice(start, end) to get substring from start to end-1.

2. Step 2: Check palindrome by reversing substring

   Reverse substring by splitting to array, reversing, then joining back to string.

3. Final Answer:

   Check if s.slice(start, end) === s.slice(start, end).split('').reverse().join('') -> Option B

4. Quick Check:

   Reverse substring and compare equals original [OK]

Hint: Reverse substring with split, reverse, join to check palindrome [OK]

Common Mistakes:

• Using slice with reversed indices (end before start)
• Trying to reverse string directly without split
• Comparing substring to reversed full string

3. What will be the output of the following code snippet?

function isPalindrome(s) {
  return s === s.split('').reverse().join('');
}

function backtrack(s, start, path, result) {
  if (start === s.length) {
    result.push([...path]);
    return;
  }
  for (let end = start + 1; end <= s.length; end++) {
    let sub = s.slice(start, end);
    if (isPalindrome(sub)) {
      path.push(sub);
      backtrack(s, end, path, result);
      path.pop();
    }
  }
}

let result = [];
backtrack('aab', 0, [], result);
console.log(result);

medium

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

B. [["aab"]]

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

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

Solution

1. Step 1: Check palindrome substrings in 'aab'

   Substrings: 'a', 'aa', 'aab', 'ab', 'b'. Palindromes are 'a', 'aa', 'b'.

2. Step 2: Backtracking builds partitions

   Partitions: ['a','a','b'] and ['aa','b'] are valid palindrome partitions.

3. Final Answer:

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

4. Quick Check:

   All palindrome partitions of 'aab' = [['a','a','b'], ['aa','b']] [OK]

Hint: Check all palindrome splits recursively to get partitions [OK]

Common Mistakes:

• Including non-palindrome substrings like 'ab'
• Missing the partition ['aa','b']
• Confusing output format with strings instead of arrays

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

function backtrack(s, start, path, result) {
  if (start > s.length) {
    result.push(path);
    return;
  }
  for (let end = start + 1; end <= s.length; end++) {
    let sub = s.slice(start, end);
    if (sub === sub.split('').reverse().join('')) {
      path.push(sub);
      backtrack(s, end, path, result);
      path.pop();
    }
  }
}

medium

A. The path array should not be mutated with push and pop

B. The substring check is incorrect; should use a separate isPalindrome function

C. The base case condition should be start === s.length, not start > s.length

D. The for loop should start from end = start, not start + 1

Solution

1. Step 1: Analyze base case condition

   Base case triggers when start > s.length, but valid partitions end exactly at start === s.length.

2. Step 2: Correct base case to push result

   Change condition to start === s.length to add current path to result correctly.

3. Final Answer:

   The base case condition should be start === s.length, not start > s.length -> Option C

4. Quick Check:

   Base case triggers at string end index [OK]

Hint: Base case must match string length exactly to save partitions [OK]

Common Mistakes:

• Using > instead of === for base case
• Not pushing a copy of path (but not asked here)
• Starting loop incorrectly at start instead of start+1

5. Given the string "racecar", how many palindrome partitions will the backtracking algorithm find?

hard

A. 8

B. 6

C. 4

D. 10

Solution

1. Step 1: Identify palindrome substrings in 'racecar'

   Palindromes include all single characters 'r','a','c','e','c','a','r'; 'cec' (indices 2-4); 'aceca' (1-5); 'racecar' (whole).

2. Step 2: Count all palindrome partitions

   Valid partitions: ['racecar'], ['r','aceca','r'], ['r','a','cec','a','r'], ['r','a','c','e','c','a','r'], and others. Total 10.

3. Final Answer:

   10 -> Option D

4. Quick Check:

   Backtracking finds 10 palindrome partitions for 'racecar' [OK]

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

Common Mistakes:

• Counting only single-character partitions
• Missing larger palindrome substrings like 'aceca'
• Assuming only 1 or 2 partitions exist