java - Find all substrings that are palindromes

Java - Find all substrings that are palindromes

Finding all substrings that are palindromes in a given string can be efficiently achieved using a dynamic programming approach. Here's a step-by-step guide on how to implement this in Java:

Approach:

  1. Dynamic Programming Setup: Use a 2D boolean array dp where dp[i][j] is true if the substring from index i to j (inclusive) is a palindrome.

  2. Palindrome Definition:

    • A single character is always a palindrome (dp[i][i] = true).
    • Two consecutive identical characters (s.charAt(i) == s.charAt(i+1)) form a palindrome (dp[i][i+1] = true).

  3. Fill the DP Table:

    • Iterate over possible lengths of substrings (len from 2 to n, where n is the length of the string).
    • For each starting index i, calculate j = i + len - 1.
    • Update dp[i][j] based on whether s.charAt(i) == s.charAt(j) and dp[i+1][j-1] is true.

  4. Extract Palindromic Substrings:

    • While filling the dp table, whenever dp[i][j] is true, record the substring from index i to j as a palindrome.

  5. Edge Cases: Handle strings of length 0 or 1 separately.

Example Implementation:

Here's a Java code snippet implementing the above approach:

import java.util.ArrayList; import java.util.List; public class PalindromicSubstrings { public List<String> getAllPalindromicSubstrings(String s) { List<String> result = new ArrayList<>(); int n = s.length(); if (n == 0) { return result; } boolean[][] dp = new boolean[n][n]; // Single character substrings are palindromes for (int i = 0; i < n; i++) { dp[i][i] = true; result.add(s.substring(i, i + 1)); // Each single character is a palindrome } // Check for substrings of length 2 for (int i = 0; i < n - 1; i++) { if (s.charAt(i) == s.charAt(i + 1)) { dp[i][i + 1] = true; result.add(s.substring(i, i + 2)); } } // Check for substrings of length >= 3 for (int len = 3; len <= n; len++) { for (int i = 0; i <= n - len; i++) { int j = i + len - 1; if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) { dp[i][j] = true; result.add(s.substring(i, j + 1)); } } } return result; } public static void main(String[] args) { PalindromicSubstrings solution = new PalindromicSubstrings(); String s = "abaaa"; List<String> palindromes = solution.getAllPalindromicSubstrings(s); System.out.println("Palindromic Substrings:"); for (String palindrome : palindromes) { System.out.println(palindrome); } } }

Explanation:

  • getAllPalindromicSubstrings Method:

    • Initializes a 2D boolean array dp to keep track of whether substrings are palindromes.
    • Iterates through different lengths of substrings (len), starting from single characters up to the length of the string.
    • Updates dp[i][j] based on conditions derived from the definition of palindromes.
    • Collects all substrings identified as palindromes in the result list.

  • Output:

    • Running the main method with the example string "abaaa" would print all palindromic substrings found: "a", "b", "aba", "aaa".

This approach efficiently finds all palindromic substrings in O(n^2) time complexity, where n is the length of the input string s. Each substring is checked and recorded only once, ensuring optimal performance.

Examples

  1. Java program to find all palindrome substrings in a string?

    • Description: Implementing a Java program to identify and print all substrings that are palindromes within a given string.
    • Code:
      public class PalindromeSubstrings { public static void main(String[] args) { String str = "ababa"; findAllPalindromeSubstrings(str); } public static void findAllPalindromeSubstrings(String str) { int n = str.length(); boolean[][] dp = new boolean[n][n]; for (int i = 0; i < n; i++) { dp[i][i] = true; } for (int i = 0; i < n - 1; i++) { if (str.charAt(i) == str.charAt(i + 1)) { dp[i][i + 1] = true; } } for (int len = 3; len <= n; len++) { for (int i = 0; i < n - len + 1; i++) { int j = i + len - 1; if (str.charAt(i) == str.charAt(j) && dp[i + 1][j - 1]) { dp[i][j] = true; } } } // Print all palindrome substrings for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { if (dp[i][j]) { System.out.println(str.substring(i, j + 1)); } } } } }

  2. Java program to find longest palindrome substring in a string?

    • Description: Writing a Java program to find the longest palindrome substring present in a given string.
    • Code:
      public class LongestPalindromeSubstring { public static void main(String[] args) { String str = "babad"; System.out.println(longestPalindromeSubstring(str)); } public static String longestPalindromeSubstring(String s) { int n = s.length(); boolean[][] dp = new boolean[n][n]; int start = 0; int maxLength = 1; for (int i = 0; i < n; i++) { dp[i][i] = true; } for (int len = 2; len <= n; len++) { for (int i = 0; i < n - len + 1; i++) { int j = i + len - 1; if (s.charAt(i) == s.charAt(j)) { if (len == 2 || dp[i + 1][j - 1]) { dp[i][j] = true; if (len > maxLength) { maxLength = len; start = i; } } } } } return s.substring(start, start + maxLength); } }

  3. Java program to count palindrome substrings in a string?

    • Description: Creating a Java program to count and print the number of palindrome substrings in a given string.
    • Code:
      public class CountPalindromeSubstrings { public static void main(String[] args) { String str = "abccba"; System.out.println(countPalindromeSubstrings(str)); } public static int countPalindromeSubstrings(String str) { int count = 0; int n = str.length(); boolean[][] dp = new boolean[n][n]; for (int i = 0; i < n; i++) { dp[i][i] = true; count++; } for (int i = 0; i < n - 1; i++) { if (str.charAt(i) == str.charAt(i + 1)) { dp[i][i + 1] = true; count++; } } for (int len = 3; len <= n; len++) { for (int i = 0; i < n - len + 1; i++) { int j = i + len - 1; if (str.charAt(i) == str.charAt(j) && dp[i + 1][j - 1]) { dp[i][j] = true; count++; } } } return count; } }

  4. Java program to find all odd length palindrome substrings?

    • Description: Implementing a Java program to identify and print all odd length palindrome substrings in a given string.
    • Code:
      public class OddLengthPalindromeSubstrings { public static void main(String[] args) { String str = "madam"; findAllOddLengthPalindromeSubstrings(str); } public static void findAllOddLengthPalindromeSubstrings(String str) { int n = str.length(); boolean[][] dp = new boolean[n][n]; for (int i = 0; i < n; i++) { dp[i][i] = true; } for (int len = 3; len <= n; len += 2) { for (int i = 0; i < n - len + 1; i++) { int j = i + len - 1; if (str.charAt(i) == str.charAt(j) && dp[i + 1][j - 1]) { dp[i][j] = true; System.out.println(str.substring(i, j + 1)); } } } } }

  5. Java program to find all even length palindrome substrings?

    • Description: Developing a Java program to find and display all even length palindrome substrings from a given string.
    • Code:
      public class EvenLengthPalindromeSubstrings { public static void main(String[] args) { String str = "noon"; findAllEvenLengthPalindromeSubstrings(str); } public static void findAllEvenLengthPalindromeSubstrings(String str) { int n = str.length(); boolean[][] dp = new boolean[n][n]; for (int i = 0; i < n; i++) { dp[i][i] = true; } for (int len = 2; len <= n; len += 2) { for (int i = 0; i < n - len + 1; i++) { int j = i + len - 1; if (str.charAt(i) == str.charAt(j) && dp[i + 1][j - 1]) { dp[i][j] = true; System.out.println(str.substring(i, j + 1)); } } } } }

  6. Java program to find the longest palindrome substring with minimum time complexity?

    • Description: Writing an efficient Java program to find the longest palindrome substring using optimal time complexity.
    • Code:
      public class LongestPalindromeSubstringEfficient { public static void main(String[] args) { String str = "racecar"; System.out.println(longestPalindromeSubstring(str)); } public static String longestPalindromeSubstring(String s) { if (s == null || s.length() < 1) return ""; int start = 0, end = 0; for (int i = 0; i < s.length(); i++) { int len1 = expandAroundCenter(s, i, i); int len2 = expandAroundCenter(s, i, i + 1); int len = Math.max(len1, len2); if (len > end - start) { start = i - (len - 1) / 2; end = i + len / 2; } } return s.substring(start, end + 1); } private static int expandAroundCenter(String s, int left, int right) { while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) { left--; right++; } return right - left - 1; } }

  7. Java program to find the number of distinct palindrome substrings?

    • Description: Creating a Java program to count the distinct palindrome substrings present in a given string.
    • Code:
      import java.util.HashSet; import java.util.Set; public class DistinctPalindromeSubstrings { public static void main(String[] args) { String str = "abccba"; System.out.println(countDistinctPalindromeSubstrings(str)); } public static int countDistinctPalindromeSubstrings(String str) { Set<String> set = new HashSet<>(); int n = str.length(); boolean[][] dp = new boolean[n][n]; for (int i = 0; i < n; i++) { dp[i][i] = true; set.add(str.substring(i, i + 1)); } for (int i = 0; i < n - 1; i++) { if (str.charAt(i) == str.charAt(i + 1)) { dp[i][i + 1] = true; set.add(str.substring(i, i + 2)); } } for (int len = 3; len <= n; len++) { for (int i = 0; i < n - len + 1; i++) { int j = i + len - 1; if (str.charAt(i) == str.charAt(j) && dp[i + 1][j - 1]) { dp[i][j] = true; set.add(str.substring(i, j + 1)); } } } return set.size(); } }

  8. Java program to find the smallest window for which all characters of a string are palindrome?

    • Description: Developing a Java program to find the smallest window in a string where all characters form a palindrome.
    • Code: (Example using a sliding window approach)
      public class SmallestPalindromeWindow { public static void main(String[] args) { String str = "abac"; System.out.println(smallestPalindromeWindow(str)); } public static String smallestPalindromeWindow(String s) { int n = s.length(); int[][] dp = new int[n][n]; for (int i = 0; i < n; i++) { dp[i][i] = 1; } for (int len = 2; len <= n; len++) { for (int i = 0; i <= n - len; i++) { int j = i + len - 1; if (s.charAt(i) == s.charAt(j)) { if (len == 2) { dp[i][j] = 2; } else if (dp[i + 1][j - 1] > 0) { dp[i][j] = dp[i + 1][j - 1] + 2; } } } } int minStart = 0, minLength = Integer.MAX_VALUE; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { if (dp[i][j] > 0 && j - i + 1 < minLength) { minStart = i; minLength = j - i + 1; } } } return s.substring(minStart, minStart + minLength); } }

  9. Java program to find longest palindromic prefix of a string?

    • Description: Implementing a Java program to find the longest palindromic prefix of a given string.
    • Code:
      public class LongestPalindromicPrefix { public static void main(String[] args) { String str = "aabcdcbaxyz"; System.out.println(longestPalindromicPrefix(str)); } public static String longestPalindromicPrefix(String s) { String rev = new StringBuilder(s).reverse().toString(); int n = s.length(); int[][] dp = new int[n + 1][n + 1]; int maxLen = 0; int endIndex = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (s.charAt(i - 1) == rev.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; if (dp[i][j] > maxLen && (i - dp[i][j] - 1 + 1 == n - j)) { maxLen = dp[i][j]; endIndex = i - 1; } } else { dp[i][j] = 0; } } } return s.substring(0, endIndex + 1); } }

  10. Java program to find all palindromic partitions of a string?

    • Description: Writing a Java program to find all possible partitions of a string where each partition is a palindrome.
    • Code:
      import java.util.ArrayList; import java.util.List; public class PalindromicPartitions { public static void main(String[] args) { String str = "nitin"; System.out.println(findAllPalindromicPartitions(str)); } public static List<List<String>> findAllPalindromicPartitions(String s) { List<List<String>> result = new ArrayList<>(); backtrack(result, new ArrayList<>(), s, 0); return result; } private static void backtrack(List<List<String>> result, List<String> tempList, String s, int start) { if (start == s.length()) { result.add(new ArrayList<>(tempList)); return; } for (int i = start; i < s.length(); i++) { if (isPalindrome(s, start, i)) { tempList.add(s.substring(start, i + 1)); backtrack(result, tempList, s, i + 1); tempList.remove(tempList.size() - 1); } } } private static boolean isPalindrome(String s, int low, int high) { while (low < high) { if (s.charAt(low++) != s.charAt(high--)) { return false; } } return true; } }

More Tags

xcode11 mediarecorder unset mach polymorphism fieldofview github-pages axis-labels floating-action-button emv

More Programming Questions

More Physical chemistry Calculators

More Various Measurements Units Calculators

More Everyday Utility Calculators

More Genetics Calculators