Strings - Valid Palindrome II

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

Input: s = "aba"
Output: true

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

Input: s = "abc"
Output: false

Constraints:

1 <= s.length <= 10⁵
s consists of lowercase English letters.

Solution 1 - Using two pointers approach

In this approach, we will use two pointers start to point beginning of the string and end to point at the end of string, and check whether the string s has palindrome properties or not by removing one character either on left side or right side.

Implementation steps:

We will first initialize two variables start = 0, and end = s.length() -1 , both points to left and right ends of the string s, and two more variables to count characters removed on left side and right side of the string charsDeletedOnLeft and charsDeletedOnRight.
While start and end do not intersect each other, read the characters and check the followng:
- If characters match on both sides : Since characters on both ends are same, increment start and decrement end.
- If characters don't match on both sides :
  - First, try removing character on right side, i.e. decrement end and increment charsDeletedOnRight by 1.
  - If removing right character already tried and still characters don't match, try removing character on left side, i.e. increment start and increment charsDeletedOnLeft by 1, but we also need to increment end, since we have already tried removing right side character, so we have to move it back to where it was.
  - If both of the above options are tried, i.e. removing a left character as well as a right character, and the characters dont match, then return false.

public class ValidPalindromeII { static boolean validPalindrome(String s) { int start = 0; int end = s.length() -1; int charsDeletedOnLeft = 0; int charsDeletedOnRight = 0; while(start < end) { if(s.charAt(start) == s.charAt(end)) { start++; end--; } else { if(charsDeletedOnRight ==0) { end--; // try removing the right side character charsDeletedOnRight++; } else if(charsDeletedOnLeft ==0) { end++;// move back since we have already tried removing one character above start++; charsDeletedOnLeft++; } else { return false; } } } return true; } public static void main(String[] args) { System.out.println(validPalindrome("race a car")); System.out.println(validPalindrome(" ")); System.out.println(validPalindrome("aba")); System.out.println(validPalindrome("abca")); System.out.println(validPalindrome("abc")); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the input string length.
Space complexity: O(1).

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: