Scale Engineer

Valid Palindrome II

Easy
#0634Time: O(N^2), where N is the length of the string. The main loop runs N times. Inside the loop, creating a new string by deleting a character takes O(N) time, and checking if the new string is a palindrome also takes O(N) time. This results in a total time complexity of O(N * N) = O(N^2).Space: O(N), where N is the length of the string. In each iteration of the loop, a new string or `StringBuilder` of length N-1 is created, requiring O(N) space.7 companies
Patterns
Two PointersGreedy
Data structures
String
Companies
Walmart LabsYandexeBayRoku

Prompt

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

 

Example 1:

Input: s = "aba"
Output: true

Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Example 3:

Input: s = "abc"
Output: false

 

Constraints:

  • 1 <= s.length <= 105
  • s consists of lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves systematically trying every possible outcome of deleting a single character from the string. For each character in the string, we remove it, create a new substring, and then check if that new substring is a palindrome. If we find any such palindrome, we can immediately return true. This method also needs to account for the case where the string is already a palindrome (zero deletions), which is covered by the 'at most one' deletion rule.

Algorithm

  • First, handle the base case of 0 deletions by checking if the original string s is a palindrome. If it is, return true.
  • Iterate through the string s with an index i from 0 to s.length() - 1.
  • In each iteration, create a temporary string by deleting the character at index i. A StringBuilder is efficient for this.
  • Check if the resulting temporary string is a palindrome using a helper function.
  • If the temporary string is a palindrome, it means we can form a palindrome by deleting one character, so return true.
  • If the loop completes without finding any such case, it means deleting one character does not help. Return false.

Walkthrough

The brute-force method is the most straightforward way to solve the problem. The core idea is to generate all possible strings that can be formed by deleting exactly one character from the original string and test each one for the palindrome property.

We can implement this with a loop that runs from the first to the last character of the string. Inside the loop, for each index i, we construct a new string that is a copy of the original but without the character at i. Then, we pass this new string to a helper function, isPalindrome, which determines if it reads the same forwards and backward.

If the helper function returns true at any point, we have found a valid scenario, and our main function can return true. If the loop finishes and we haven't found a palindrome, it means deleting one character is not sufficient. We also need to consider the case where zero deletions are needed, i.e., the original string is already a palindrome. A simple way to structure the logic is to first check the original string, and if it's not a palindrome, then proceed with the loop to check for one-deletion palindromes.

class Solution {    public boolean validPalindrome(String s) {        // Case for 0 deletions        if (isPalindrome(s, 0, s.length() - 1)) {            return true;        }         // Case for 1 deletion        for (int i = 0; i < s.length(); i++) {            // Create a new string by deleting the character at index i            StringBuilder sb = new StringBuilder(s);            sb.deleteCharAt(i);            if (isPalindrome(sb.toString(), 0, sb.length() - 1)) {                return true;            }        }                return false;    }     private boolean isPalindrome(String str, int left, int right) {        while (left < right) {            if (str.charAt(left) != str.charAt(right)) {                return false;            }            left++;            right--;        }        return true;    }}

Complexity

Time

O(N^2), where N is the length of the string. The main loop runs N times. Inside the loop, creating a new string by deleting a character takes O(N) time, and checking if the new string is a palindrome also takes O(N) time. This results in a total time complexity of O(N * N) = O(N^2).

Space

O(N), where N is the length of the string. In each iteration of the loop, a new string or `StringBuilder` of length N-1 is created, requiring O(N) space.

Trade-offs

Pros

  • Conceptually simple and easy to understand.

  • Straightforward to implement.

Cons

  • Highly inefficient due to O(N^2) time complexity.

  • Will likely result in a 'Time Limit Exceeded' error for large inputs as specified in the constraints (N up to 10^5).

Solutions

/** * @param {string} s * @return {boolean} */ var validPalindrome = function (  s,) {  let check = function (i, j) {    for (; i < j; ++i, --j) {      if (s.charAt(i) != s.charAt(j)) {        return false;      }    }    return true;  };  for (let i = 0, j = s.length - 1; i < j; ++i, --j) {    if (s.charAt(i) != s.charAt(j)) {      return check(i + 1, j) || check(i, j - 1);    }  }  return true;};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem