Palindrome

Palindrome Number Problem

Problem Determine whether an integer is a palindrome. Follow up Do this without extra space. Definition Palindrome Definition Examples Example 1: Input: x = 121 Output: true Explanation: 121 reads as 121 from left to right and from right to left. Example 2: Input: x = -121 Output: false Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome. ...

Longest Palindrome Problem

Problem Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters. Letters are case sensitive, for example, "Aa" is not considered a palindrome here. Examples Example 1: Input: s = "abccccdd" Output: 7 Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7. ...

Palindrome Partitioning Problem

Problem Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Definition Palindrome Definition Examples Example 1: Input: s = "aab" Output: [ ["a","a","b"],["aa","b"] ] Example 2: Input: s = "a" Output: [ ["a"] ] ...

Longest Palindromic Substring Problem

Problem Given a string s, return the longest palindromic substring in s. Incase of conflict, return the substring which occurs first ( with the least starting index ). Substring of string S: S[i...j] where 0 <= i <= j < len(S) Example Example 1: Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer. ...

Check if given string is palindrome or not

Problem Write an algorithm to find Whether Given String is palindrome or Not. Definition Palindrome Definition Examples Example 1: Input: str = "malayalam" Output: true Example 2: Input: str = "abc" Output: false Solution Method 1 - Recursion Algorithm If the first and last characters don’t match, return false (not a palindrome). If they match, remove the first and last characters and call the function recursively with the remaining substring. This continues until the entire string is checked. Code Java public Boolean isPalindrome(String s) { if (s.length()<2) { return true; } if (s.charAt(0) == s.charAt(s.length() - 1)) { return isPalindrome(s.substring(1, s.length() - 1)); } else { return false; } } ...

Valid Palindrome Problem

Problem Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. Palindrome Definition Examples 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. ...

Manachar’s Algorithm - Longest palindromic substring in linear time

Problem Given a string, find the longest palindromic substring in linear time i.e. substring that is also a palindrome. Subsequently, Find all palindromic substrings of a given string We have already seen simple O(n^2) solution here - Longest Palindromic Substring Problem, but now lets look at Manacher’s Algorithm, which help us find the solution in linear time. Manacher’s Algorithm #TODO complete this

Valid Palindrome 2 Problem

Problem Given a string s, return true if the s can be palindrome after deleting at most one character from it. Examples Example 1: Input: s = "aba" Output: true Example 2: Input: s = "abca" Output: true Explanation: You could delete the character 'c'. ...

Palindrome Linked List Problem

Problem Given the head of a singly linked list, return true if it is a palindrome or false otherwise. Examples Example 1: Input: head = [1,2,2,1] Output: true head = 1 -> 2 -> 2 -> 1 Example 2: Input: head = [1,2] Output: true head = 1 -> 2 ...

Check if given array is Palindrome OR Not

Check if Given Array is Palindrome OR Not Problem Given an array, the task is to determine whether an array is a palindrome or not. Examples Example 1: Input: arr[] = {3, 6, 0, 6, 3} Output: true Example 2: Input: arr[] = {1, 2, 3, 4, 5} Output: false ...