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

Bmw Inpa F&e Series Download

Have Yourself a Matrix LED Christmas

How Python is useful in Machine learning

Kafka: Let it Flow

How Recommendation Engine can be improved drastically?

Ark Sidechain — Azure Quickstart

How to manually invalidate AWS CloudFront

Why Working Software is One of the Primary Principles of Agile

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

Corona infection in a gated community/society

ARTS Week 23

Validate Binary Search Tree

Binary Tree