`{"id":"4d042587-3fa1-4d0e-8a42-a534477b2c0c","name":"Manacher's Algorithm","description":"1. You are given one string s1.\r\n2. You have to find the longest palindromic substring in s1.\r\n3. Expected Complexity : O(n)","inputFormat":"one string s1","outputFormat":"Print the length of the longest palindrome substring in the first line. In the second line print the longest palindromic substring in s1. If there is more than one palindromic substring with the maximum length, output the first one.","constraints":"1 &lt;= length of the string &lt;= 10^5","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void solution(String s1) {\r\n // write your code here\r\n\r\n }\r\n \r\n public static void main(String[] args) {\r\n Scanner scn = new Scanner(System.in);\r\n String s1 = scn.next();\r\n solution(s1);\r\n System.out.println();\r\n\t}\r\n\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"abadxd","sampleOutput":"3\r\naba","questionVideo":"https://www.youtube.com/embed/06QIlUBLTz4","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"a2073e25-96a1-4875-b400-f40bbe2edd95","name":"Text Processing For Experts","slug":"text-processing-for-experts-859","type":0},{"id":"e5a74cfe-994f-4a66-9b70-d2a5c9de4df8","name":"Manacher's Algorithm","slug":"manacher-s-algorithm","type":1}],"next":{"id":"4db1ece4-b806-4cd6-bea3-c8b8a8e88932","name":"String Rotation","type":1,"slug":"string-rotation"},"prev":{"id":"4d156fb0-c2a3-4503-9fee-4c666d62cc6f","name":"Find String Roots","type":1,"slug":"find-string-roots"}}}`

# Manacher's Algorithm

1. You are given one string s1. 2. You have to find the longest palindromic substring in s1. 3. Expected Complexity : O(n)

`{"id":"4d042587-3fa1-4d0e-8a42-a534477b2c0c","name":"Manacher's Algorithm","description":"1. You are given one string s1.\r\n2. You have to find the longest palindromic substring in s1.\r\n3. Expected Complexity : O(n)","inputFormat":"one string s1","outputFormat":"Print the length of the longest palindrome substring in the first line. In the second line print the longest palindromic substring in s1. If there is more than one palindromic substring with the maximum length, output the first one.","constraints":"1 &lt;= length of the string &lt;= 10^5","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void solution(String s1) {\r\n // write your code here\r\n\r\n }\r\n \r\n public static void main(String[] args) {\r\n Scanner scn = new Scanner(System.in);\r\n String s1 = scn.next();\r\n solution(s1);\r\n System.out.println();\r\n\t}\r\n\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"abadxd","sampleOutput":"3\r\naba","questionVideo":"https://www.youtube.com/embed/06QIlUBLTz4","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"a2073e25-96a1-4875-b400-f40bbe2edd95","name":"Text Processing For Experts","slug":"text-processing-for-experts-859","type":0},{"id":"e5a74cfe-994f-4a66-9b70-d2a5c9de4df8","name":"Manacher's Algorithm","slug":"manacher-s-algorithm","type":1}],"next":{"id":"4db1ece4-b806-4cd6-bea3-c8b8a8e88932","name":"String Rotation","type":1,"slug":"string-rotation"},"prev":{"id":"4d156fb0-c2a3-4503-9fee-4c666d62cc6f","name":"Find String Roots","type":1,"slug":"find-string-roots"}}}`

Editor

# Manacher's Algorithm

hard

1. You are given one string s1. 2. You have to find the longest palindromic substring in s1. 3. Expected Complexity : O(n)

## Constraints

1 <= length of the string <= 10^5

## Format

one string s1

### Output

Print the length of the longest palindrome substring in the first line. In the second line print the longest palindromic substring in s1. If there is more than one palindromic substring with the maximum length, output the first one.

## Example

Sample Input

`.css-23h8hz{color:inherit;font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;}abadxd`

### Sample Output

```.css-3oaykw{color:var(--chakra-colors-active-primary);font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;font-family:Monospace;}3 aba```

Question Video

Discussions

Show Discussion

Related Resources