Valid Palindrome with Removal
1 min read

Valid Palindrome with Removal

Valid Palindrome II

Given a string and the ability to delete at most one character, return whether or not it can form a palindrome.
Note: a palindrome is a sequence of characters that reads the same forwards and backwards.

Ex: Given the following strings...

"abcba", return true
"foobof", return true (remove the first 'o', the second 'o', or 'b')
"abccab", return false
    fun validPalindrome(s: String): Boolean {
        var (start, end) = 0 to s.length-1
        while(start < end) {
            if(s[start++] != s[end--]) {
                return isPalindrome(s,start,end+1) || isPalindrome(s,start-1,end)
            }
        }
        return true
    }
    
   private fun isPalindrome(s: String, start: Int, end: Int) : Boolean {
        var (start, end) = start to end
        while(start < end) {
            if(s[start++] != s[end--])  return false
        }
        return true
    }

The idea here is to traverse a string from both the ends . Let’s say the two variables are start and end. The initial values of start and end are 0 and string length minus one.

Run a loop and start comparing characters present at start and end index.  If it is not equal then check whether a string is palindrome by deleting either the character present at left or right index.

If it’s not equal then return false, else return true.

The time complexity of this approach is O(n) and it’s space complexity is O(1).

Enjoying these posts? Subscribe for more