# 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).