Valid Palindrome II

Photo by Sangga Rima Roman Selia on Unsplash

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.

Solution

  1. Initialize the left and right pointers at each end of the array, respectively.
  2. Traverse the array until left is less than right.
  3. If the element pointed to by the left pointer is equal to the element pointed to by the right pointer, do the following:
  • Increment the left pointer by one position.
  • Decrement the right pointer by one position.

4. If the element pointed to by the left pointer is not equal to the element pointed to by the right pointer, do the following:

  • Ignore the value at the left pointer by checking if the elements at indexes left + 1 to right form a palindrome or not. If they do, return true; this indicates the presence of only one diversion router.
  • Ignore the value at the right pointer by checking if the elements at indexes left to right - 1 form a palindrome or not. If they do, return true; this indicates the presence of only one diversion router.

5. If both of the above cases fail, return false; this indicates the presence of multiple diversion routers.

6. If no mismatch occurs, return true; this indicates the presence of a zero-diversion router.

Time complexity

The time complexity will be O(n) because the array is only traversed once.

Space complexity

The space complexity will be O(1) because we only manipulate some pointers.

--

--

--

Full Stack Programmer, love to solve problem’s during free time.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Simplifying Regular expressions in javascript.

Using FullCalendar with Rails/React

Awesome Vue.js Open Source Projects

All you need to know about TypeScript’s CORE Types.

TIL/2020–12–25

How to make a basic React website

Replace Object with Map in your JavaScript code

Front-end State Containers: Effective Selection

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jaydeep

Jaydeep

Full Stack Programmer, love to solve problem’s during free time.

More from Medium

Linked List — A brief theoretical FAQ for Placement Interviews

An Introduction to Linked Lists

Merge Sort for Linked Lists

Minimum Depth of Binary Tree🛩