algoadvance

Leetcode 131. Palindrome Partitioning

Problem Statement

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Example:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Clarifying Questions

1. What is the length of the string s?
   • This will help us understand the constraints and expected time complexity.
2. Are there any constraints on the characters in the string?
   • Usually, strings are composed of lowercase English letters.
3. Should the partitions contain all possible palindromes, including single characters?
   • By the problem statement, yes, all characters and possible palindromes should be included.

Strategy

1. Backtracking Approach:
   • We will use a backtracking approach to explore all possible partitions.
   • For each position in the string, we will check if the substring up to that point is a palindrome.
   • If it is, we will recurse with the remaining part of the string.
   • We will use a helper function to check if a given substring is a palindrome.
2. Helper Function isPalindrome:
   • This function will take a substring and return whether it is a palindrome.
3. Backtracking Function backtrack:
   • This will recursively partition the string and store valid partitions if the substring is a palindrome.
4. Base Case:
   • If we reach the end of the string, we add the current partition to the result list.

Code

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(String s, int start, List<String> currentList, List<List<String>> result) {
        if (start == s.length()) {
            result.add(new ArrayList<>(currentList));
            return;
        }
        
        for (int end = start + 1; end <= s.length(); end++) {
            if (isPalindrome(s, start, end - 1)) {
                currentList.add(s.substring(start, end));
                backtrack(s, end, currentList, result);
                currentList.remove(currentList.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s, int low, int high) {
        while (low < high) {
            if (s.charAt(low++) != s.charAt(high--)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        String s = "aab";
        List<List<String>> result = sol.partition(s);
        System.out.println(result);
    }
}

Time Complexity

• Backtracking Complexity: The time complexity is quite high due to the exponential number of partitions; each character has a decision to either start a new partition or continue with the previous one.
  • If there are n characters, there are 2^(n-1) ways to partition n characters.

• Palindrome Check Complexity: Checking each substring if it’s a palindrome takes O(n) time.

• Total Complexity: In the worst case, for each possible partition, we are checking if the substring is a palindrome. If n is the length of the string:
  • Total time complexity is approximately O(n * 2^n).

While this approach can handle small strings effectively, it might not scale well for very large strings due to the exponential nature of the problem.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?