125. Valid Palindrome
Valid Palindrome (LeetCode 125) 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.
- Blind 75 · #9 of 75 · Two Pointers
- NeetCode 150 · #10 of 150 · Two Pointers
- NeetCode 250 · #24 of 250 · Two Pointers
How to solve Valid Palindrome
Valid Palindrome 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 which data structure or technique can help you efficiently check if a string reads the same forwards and backwards.
- Think about preprocessing the string to remove all characters that are not letters or digits, and converting all letters to the same case.
- How can you use two pointers starting from the beginning and end of the processed string to compare characters without extra space?
The reference solution runs in O(n) time and O(1) space.
The Valid Palindrome solution and editorial walks through the full approach with reference code.
Problem statement
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
Example 1:
Input: s = "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama" is a palindrome.
Example 2:
Input: s = "race a car" Output: false Explanation: "raceacar" is not a palindrome.
Example 3:
Input: s = " " Output: true Explanation: s is an empty string "" after removing non-alphanumeric characters. Since an empty string reads the same forward and backward, it is a palindrome.
Constraints:
- 1 <= s.length <= 2 105
- s consists only of printable ASCII characters.
Topics and companies
Topics: Two Pointers, String.
Reported in interviews at Facebook, Microsoft, Apple, Wayfair, Amazon, Yandex, Bloomberg, Oracle.
How to practise Valid Palindrome 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 in the code editor, or read the Valid Palindrome editorial for a worked solution with its approach and complexity analysis.
Where Valid Palindrome 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
Other problems that use the same Palindrome Check (Two Pointers / Reverse) and String Manipulation Patterns techniques:
- Palindrome Number — Easy, same subpattern
- Valid Palindrome II — 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 FAQ
What is the LeetCode number of Valid Palindrome?
Valid Palindrome is LeetCode problem 125, rated Easy.
What pattern is used to solve Valid Palindrome?
Valid Palindrome 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?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Valid Palindrome?
Valid Palindrome has been reported in interviews at Facebook, Microsoft, Apple, Wayfair, Amazon, Yandex, Bloomberg, Oracle.