educative.io

Educative

Any other optimized ways to solve Valid Palindrome II

Courses
,
#1
  • My approach is to maintain two variables, leftSkip, and rightSkip.
  • leftSkip = 0, if found any condition where value[left_index] != value[right_index]
    1. increment the left_index if leftSkip = 0 (one character needs to be removed, so skip the left character)
    2. increment the leftSkip then break(indicates more than one character needs to be removed)
  • rightSkip = 0, if found any condition where value[left_index] != value[right_index]
    1. decrement the right_index if rightSkip = 0 (one character needs to be removed, so skip the right character)
    2. increment the rightSkip then break(indicates more than one character needs to be removed)
  • check if leftSkip <=1 || rightSkip <=1, return true
  • return false

Any other approach or any pointers on this approach is much appreciated

Course: https://www.educative.io/courses/grokking-coding-interview-patterns-cpp
Lesson: Valid Palindrome II - Grokking Coding Interview Patterns in C++

#3

Hi @Prasanna_Reddy_Isire,
We suggest you to write a code and run it in the Try it yourself section. If your code passes all the test cases, then definitely your code and logic are correct. You must keep moving the left and right pointer until it doesn’t match. After that, you must delete the element, pointing by the left or right pointer if the given palindrome is valid.
For example, ABDDEBA
In the above example, your left pointer would be at 1st D, and the right pointer would be at E. So, you have to compare the left pointer element with the next element and the right pointer element with the previous one to find out which element should be deleted. If out of the above two comparisons, any of the elements match, that means the given palindrome is a valid palindrome(if the element at the left pointer matches with its next element, then delete the element at the right pointer)