100 Days to crack FAANG interview Day 4 — Palindrome Partitioning

Welcome to Day 4 of my FAANG/MAANG interview preparation journey! Today, I’ve decided to tackle a medium-level problem for the first time.

Problem Statement:

Palindrome Partitioning — https://leetcode.com/problems/palindrome-partitioning/

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”]]

Approach

To solve this problem, we can traverse the input string from left to right till we encounter a palindrome substring. Once we find a palindrome substring, we recursively generate all possible palindrome partitions for the remaining substring. The current palindrome substring should be then added to each partition list and continue this process until we reach the end of the string.

Code Implementation

public boolean isPalindrome(String s) {
  for(int i=0;i<s.length();i++) {
    if(s.charAt(i) != s.charAt(s.length()-1-i)) return false;
  }
  return true;
}

public List<List<String>> partition(String s) {
  List<List<String>> result = new ArrayList<>();
  for(int i=1;i<=s.length();i++) {
    String s2 = s.substring(0, i);
    if(!isPalindrome(s2)) continue;

    if(i==s.length()) {
      List<String> result1 = new ArrayList<>();
      result1.add(s);
      result.add(result1);
      continue;
    }

    List<List<String>> result2 = partition(s.substring(i));
    for(List<String> innerResult: result2) {
      innerResult.add(0, s2);
      result.add(innerResult);
    }

  }
  return result;
}

The low runtime is most likely due to the lack of memoization. In my current implementation, we end up computing the palindrome partition repeatedly for the same substring, which can significantly impact performance. Storing the results of the previously computed palindrome will reduce the overall runtime. I’ll work on incorporating memoization later.

FAANG Interview Preparation Guide