GFG POTD: Palindrome Pairs | Constructive (Java) | Day 16

Welcome to today's explanation of the GFG POTD (Problem of the Day)! In this video, I break down the strategies, ideas, and core concepts you need to solve the "Palindrome Pairs" problem. Understanding string manipulation, HashMaps, and prefix/suffix palindromic checks will massively boost your overall problem-solving skills and help you build the solid foundation needed to tackle complex string-matching questions next time. If you found this video helpful, please show your gratitude by liking the video, and don't forget to subscribe to the channel for more daily coding content. Happy coding! Problem Name: Palindrome Pairs Difficulty: Hard Platform: GeeksforGeeks Question: Determine whether there exists a pair of indices (i, j) from an array of n strings such that i ≠ j and the concatenation of arr[i] + arr[j] forms a palindrome. The Approach (HashMap Lookups & Prefix/Suffix Partitioning) 1 . Understand the Brute Force Bottleneck: Checking every single combination of string pairs requires nested loops, leading to an O(N^2 * K) time complexity (where N is the number of strings and K is the average length). For 20,000 strings, this will result in a Time Limit Exceeded (TLE) error. We need a more optimized approach! 2. Build a Reverse Lookup Map: Instead of checking a string against every other string, we can work backward. We reverse every string in the array and store it in a HashMap along with its original index. This allows us to instantly look up if the exact required matching string exists in our array. 3. Split and Check (Prefix and Suffix): We iterate through each string in the array. For every string, we partition it into two parts: a prefix (u) and a suffix (v). We do this for every possible split point from index 0 to the length of the string. 4. Two Key Conditions for a Match: Condition 1: If the prefix (u) is already a palindrome, we just need to find a string in our map that matches the suffix (v). If it exists (and it's not the current string itself), we have found a valid pair! Condition 2: Similarly, if the suffix (v) is a palindrome, we check if the map contains a match for the prefix (u). If it does, that's also a valid palindrome pair! Time Complexity: O(N * K^2) where N is the total number of strings in the array and K is the maximum length of a string. Building the map takes O(N * K). Iterating through the array, splitting strings, and checking palindromes/map lookups takes O(N * K^2). Given the constraint that string lengths are very small (K ≤ 10), this runs exceptionally fast and behaves almost like O(N) Space Complexity: O(N * K) to store the reversed strings and their corresponding indices inside the HashMap. Solution Code: https://github.com/Arnab-Pachal1234/GFG-POTD-SOLUTION #gfg #dsa #string #hashmap #palindromepairs #coding #problemoftheday #java #hardquestion #leetcode #competitiveprogramming #datastructures #algorithm