680. Valid Palindrome II - LeetCode Fastest Solution

Hello Code Recipian! Welcome back to another article on LeetCode problem solutions. In our last article we solved LeetCode problem 125. Valid Palindrome. Today we will be solving an extension of this problem 680. Valid Palindrome II.

If you have not yet checked out 125. Valid Palindrome, this is a good time to go through it, before proceeding further in this article.

Problem Statement: Valid Palindrome II

Given string s, return true if it is possible to make s a palindrome by removing at-most one character from s.

A string is a palindrome if it reads the same forward and backward.

Example 1:

Input: s = "aba"
Output: true
Explanation: s is already a palindrome.

Example 2:

Input: s = "abca"
Output: true
Explanation: We can delete the character 'c' to make s a palindrome.

Example 3:

Input: s = "abc"
Output: false
Explanation: s is not a palindrome and cannot be made palindrome by deleting any one character.

Constraints:

• 1 <= s.length <= 10^5

• s consists of lowercase English letters.

Solution

We can use the same two pointer technique that we used for solving 125. Valid Palindrome here as well with a slight modification. We will be using the two pointer technique along with greedy approach to solve this problem efficiently in linear time.

Let's see how this algorithm works in detail.

Algorithm

Below is a step-by-step explanation for the working of the algorithm:

1. Initialization:

   Initialize two variables: start, end.

   1. start represents the index of the variable used to iterate the string from starting index. This is initially set to the 0th index.

   2. end represents the index of the variable used to iterate the string from the end. This is initially set to the last index.

2. Check if s is a palindrome:

   Start iterating the string inwards using start, end index variables. In each iteration perform the following steps:

   1. Check if characters represented by start and end indices match.

      1. If yes, continue iterating inwards through the string s.

      2. If no, we have 2 choices:

         1. Skip the start character and continue checking for a palindrome.

         2. Skip the end character and continue checking for palindrome.

         3. If any of these choices returns a true, it means we can form a palindrome by skipping one character. Therefore return true.

         4. If both choices return false, it means palindrome cannot be formed by skipping one character in string s. Therefore return false.

3. Return result:

   If the execution comes out of main loop, it means we have checked all characters in string s and all of them match, therefore s is a palindrome. Therefore, we return result as true.

Simulation

Below is a pictorial depiction of the working of the algorithm:

Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses:

1. Udemy Video Tutorials - Available at 95% off

2. System Design Interview Complete Guide

3. Cracking The Coding Interview - Most Preferred Book For Coding Interviews

4. Data Structures And Algorithms - A Complete Guide 

5. Learn In-Demand Tech Skills And Stay Ahead Of Others

Code

Go Solution

Python Solution

Java Solution

JavaScript Solution

TypeScript Solution

C++ Solution

C# Solution

C Solution

PHP Solution

Kotlin Solution

Swift Solution

Ruby Solution

Scala Solution

Rust Solution

Complexity Analysis

Time Complexity

We make use of two loops here, one in the main function and one in the helper function, effectively it is a nested loop. The helper function can get called from the main loop at-most twice. If n is the length of the given string s, if the first loop iterates through x elements of string s, and then calls the helper function. The helper function runs for the remaining (n-x) elements, and it runs twice in the worst case. So the overall time complexity if O(x + 2 * (n-x)) = O(2n - x) which is asymptotically equivalent to O(n).

Space Complexity

The space complexity of this solution is O(1) as we are not using any additional variables apart from start and end which take constant space.

That brings us to the end of this article. We appreciate the time you have taken to read through it. If you have any questions, feel free to ask them in the comments below. We're here to help and will gladly answer your queries.

If you enjoyed this article, please subscribe to our website and Youtube channel. Your support inspires us to bring out more such articles in future.

Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section. There's a wealth of knowledge waiting for you there!

Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now.

Follow us: YouTube, Facebook, Twitter, LinkedIn, Tumblr, Instagram.