680. Valid Palindrome II
Valid Palindrome II (LeetCode 680) is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the String Manipulation Patterns pattern, in the Palindrome Check (Two Pointers / Reverse) subpattern.
How to solve Valid Palindrome II
Valid Palindrome II is a Palindrome Check problem, part of String Manipulation Patterns. Master palindrome checking using two pointers. Handle valid palindrome with alphanumeric and one removal cases.
Work towards the solution in these steps:
- Consider using a two-pointer technique to check if a string is a palindrome efficiently.
- Start by comparing characters from the beginning and end of the string, moving pointers inward.
- If you find mismatching characters, think about the effect of removing one of them and checking if the rest forms a palindrome.
The reference solution runs in O(n) time and O(1) space.
The Valid Palindrome II solution and editorial walks through the full approach with reference code.
Problem statement
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.
Topics and companies
Topics: Two Pointers, String, Greedy.
Reported in interviews at Facebook, Oracle, Microsoft, eBay, Wish.
How to practise Valid Palindrome II on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Valid Palindrome II in the code editor, or read the Valid Palindrome II editorial for a worked solution with its approach and complexity analysis.
Where Valid Palindrome II sits in the DSA pattern sheet
- String Manipulation Patterns pattern guide
- Palindrome Check (Two Pointers / Reverse) subpattern
- The full DSA patterns sheet
Problems related to Valid Palindrome II
Other problems that use the same Palindrome Check (Two Pointers / Reverse) and String Manipulation Patterns techniques:
- Palindrome Number — Easy, same subpattern
- Valid Palindrome — Easy, same subpattern
- Add Strings — Easy, same pattern
- Excel Sheet Column Title — Easy, same pattern
- Find Beautiful Indices in the Given Array II — Hard, same pattern
- Find the Index of the First Occurrence in a String — Easy, same pattern
Valid Palindrome II FAQ
What is the LeetCode number of Valid Palindrome II?
Valid Palindrome II is LeetCode problem 680, rated Easy.
What pattern is used to solve Valid Palindrome II?
Valid Palindrome II is a Palindrome Check problem. It belongs to the String Manipulation Patterns pattern, in the Palindrome Check (Two Pointers / Reverse) subpattern.
What is the time complexity of Valid Palindrome II?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Valid Palindrome II?
Valid Palindrome II has been reported in interviews at Facebook, Oracle, Microsoft, eBay, Wish.