Symmetry in Strings

 Longest Palindromic Substring 

This might seem like a string manipulation task at first, but it's a golden opportunity to understand techniques like brute force exploration, expanding from center, and dynamic programming — all while strengthening your grip on substring logic and indexing.

Let’s explore how to solve this problem using three different approaches: brute force, expand around center, and dynamic programming.

The Best Data Structure for Solving It (And Why!)

When dealing with substrings, two things are crucial:

  • Knowing how to efficiently iterate through all possible substrings.

  • Being able to check if a substring is a palindrome in a smart way.

Brute force gives us the raw idea.
Expand-around-center improves on it with a clever trick.
Dynamic programming brings in structure and memory for optimization.

Let’s dive in!

Different Approaches – From Brute Force to Optimized

1)Brute Force (Naive Approach)

This approach checks all possible substrings and verifies whether they are palindromes. It keeps track of the longest one found.

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        String longest = "";
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                String sub = s.substring(i, j + 1);
                if (isPalindrome(sub) && sub.length() > longest.length()) {
                    longest = sub;
                }
            }
        }
        return longest;
    }

    private boolean isPalindrome(String str) {
        int left = 0, right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left++) != str.charAt(right--)) return false;
        }
        return true;
    }
}

Explanation:

  • We loop through all substrings of s using two nested loops.

  • For each substring, we check if it’s a palindrome.

  • If it is, and it’s longer than our previous result, we update our result.

2)Expand Around Center (Optimized O(n²))

This approach builds on the fact that a palindrome mirrors around its center. We try to expand from every character (and the gap between characters) as a center and find the maximum length.

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";

        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandFromCenter(s, i, i);       // Odd length
            int len2 = expandFromCenter(s, i, i + 1);   // Even length
            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 int expandFromCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

Explanation:

  • We treat each index and gap between characters as a center.

  • Expand as long as the characters at both ends match.

  • Keep track of the longest palindrome found.

3)Dynamic Programming

Here we use a 2D boolean table dp[i][j] to represent whether the substring from index i to j is a palindrome. We build the solution by checking increasing lengths.


class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        String result = "";

        for (int l = 0; l < n; l++) {
            for (int i = 0; i < n - l; i++) {
                int j = i + l;
                if (s.charAt(i) == s.charAt(j) && (l < 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    if (l + 1 > result.length()) {
                        result = s.substring(i, j + 1);
                    }
                }
            }
        }

        return result;
    }
}

Explanation:

  • We start with substrings of length 1 and build up.

  • If characters at the ends match and the inside is a palindrome, the whole thing is.

  • Track and return the longest one found.

⚠️ Common Mistakes & Pitfalls to Avoid

  • Forgetting Even-Length Palindromes: Don't just expand around single characters — check between them too!

  • Off-by-One Errors: Especially with substring indices in Java — remember it's exclusive at the end.

  • Inefficient Checking: In brute force, checking every substring without memoization becomes slow very quickly.

📊 Time and Space Complexity Analysis

Brute Force:

  • Time: O(n³) — generating substrings and checking if they’re palindromes

  • Space: O(1) if you don’t count the result string

Expand Around Center:

  • Time: O(n²)

  • Space: O(1)

Dynamic Programming:

  • Time: O(n²)

  • Space: O(n²) for the DP table

🌍 Real-World Applications

Finding palindromic substrings isn't just academic — it shows up in:

  • DNA Analysis: Where palindromic sequences have biological significance

  • Data Compression: Where repeated patterns are exploited

  • Text Processing: For finding symmetries or patterns in documents and logs


I hope you found this article insightful! Keep exploring, keep learning, and don’t forget to check back daily for more exciting problem breakdowns. If you know someone who would benefit from this, share it with them and help them grow too! That’s it for today—see you in the next post!

                                                                                                                                         Signing off!! 

                                                                                                Master DSA One Problem at a Time :)

Comments

Post a Comment

Popular posts from this blog

Trailing Zeros in Factorial – How Many and Why?

Trailing Zeros – Counting Zeros in Factorial Factorial-related problems are a fundamental part of Data Structures and Algorithms (DSA). One such classic problem involves counting the number of trailing zeros in N! . In this article, we will explore different approaches to solving this problem, optimize our solution, and examine its real-world applications. Optimal Data Structure for Solving the Problem For this problem, no additional data structures are required. Since factorials grow exponentially, storing the actual factorial value is impractical. Instead, we leverage mathematical properties and division operations to efficiently determine the number of trailing zeros. This approach ensures an optimal solution in terms of both time and space complexity. Approach – From Brute Force to an Optimized Solution Brute Force Approach – Compute and Count A naive approach involves computing the factorial of N and counting the number of trailing zeros. However, this method is highly ineff...
Read more

Divisible Drama — Who’s In, Who’s Out?

 Divisible Drama — Who’s In, Who’s Out? Problem Statement You’re given two positive integers n and m . num1 = sum of all numbers from 1 to n not divisible by m num2 = sum of all numbers from 1 to n divisible by m Your mission, should you choose to accept it: Return num1 - num2 Example Input: n = 10 , m = 3 Output: 19 Breakdown: Not divisible by 3 → [ 1 , 2 , 4 , 5 , 7 , 8 , 10 ] → num1 = 37 Divisible by 3 → [ 3 , 6 , 9 ] → num2 = 18 Answer = 37 - 18 = 19 Best Data Structure for Solving the Problem This one’s a math.  Why overthink it when Gauss already gave us the formula for sum of 1 to n? Different Approaches (from Brute Force to Optimized) Approach 1: Brute Force (aka List & Sum Vibes) Loop from 1 to n , split the nums based on whether they’re divisible by m , and sum them up. class Solution { public int differenceOfSums ( int n, int m) { int num1 = 0 , num2 = 0 ; for ( int i = 1 ; i <= n; i++)...
Read more

Zero Array After Queries

Zero Array After Queries You are given an integer array nums and a list of queries, where each query is a pair [li, ri] representing a range. Each query allows you to decrement any subset of elements in the range [li, ri] by 1. Your task is to determine if it is possible to make every element in nums equal to zero after applying all queries in order . Example Input: nums = [ 1 , 0 , 1 ] queries = [[0, 2]] Output: true Explanation: We can select indices 0 and 2 and decrement both by 1 to obtain [0, 0, 0] . Best Data Structure for the Job We are working with multiple range updates and need to evaluate coverage over indices. The best choice here is the difference array combined with a prefix sum . It allows efficient range additions and helps track how many times each index is affected by the queries. Different Approaches Approach 1: Brute Force This naive method iterates over every index for every query and performs the decrement operations directly. class Solution {...
Read more