Starting from a string, we have to find the longest substring which is a palindrome.
Input: String input = "skjrefactorbrotcaferjiji"; Output: jrefactorbrotcaferj Explanation: The word jrefactorbrotcaferj reads the same backwards as forwards, and is the largest palindromic substring in the word skjrefactorbrotcaferjiji. |
Solution:
1. static String longestPalindromicSubstring(String input) { 2. int inputLength = input.length(); 3. 4. boolean[][] palindromes = new boolean[inputLength][inputLength]; 5. 6. int palindromeLength = 1; 7. for (int i = 0; i < inputLength; ++i) { 8. palindromes[i][i] = true; 9. } 10. 11. int start = 0; 12. for (int i = 0; i < inputLength - 1; ++i) { 13. if (input.charAt(i) == input.charAt(i + 1)) { 14. palindromes[i][i + 1] = true; 15. start = i; 16. palindromeLength = 2; 17. } 18. } 19. 20. for (int k = 3; k <= inputLength; ++k) { 21. for (int i = 0; i < inputLength - k + 1; ++i) { 22. int j = i + k - 1; 23. if (palindromes[i + 1][j - 1] && input.charAt(i) == input.charAt(j)) { 24. palindromes[i][j] = true; 25. if (k > palindromeLength) { 26. start = i; 27. palindromeLength = k; 28. } 29. } 30. } 31. } 32. 33. return input.substring(start, start + palindromeLength); 34. } 35.
Comentários