Day 23 - Java

Problem Statement: Palindrome Chain Transformer

You are given a list of strings. For each string, transform it into a palindrome by appending the minimum number of characters to its end. If a string is already a palindrome, leave it as is.

Once all strings are transformed, compress the transformed list into a "Palindrome Chain Representation" as follows:

1. For the first occurrence of a palindrome, retain the entire palindrome string.
2. For subsequent occurrences of the same palindrome, replace it with the index (0-based) of its first occurrence in the transformed list.

Write a program to process the input strings, generate the transformed palindromes, and return the compressed representation.

Input Format

A single line containing space-separated strings.

• Each string consists of 1 to 20 lowercase English letters.
• There are 1 to $10^4$ strings.

Output Format

A single line containing space-separated values representing the "Palindrome Chain Representation."

• The output can contain transformed palindromes or indices (0-based).

Constraints

• Strings are case-sensitive.
• The number of strings will not exceed $10^4$.

Sample Test Cases

Sample Input 1

abc racecar abba car racecar abcba ab

Sample Output 1

abccba racecar abba carac racecar abcba abba 1

Sample Input 2

aaa bbb ccc aaa ccc

Sample Output 2

aaa bbb ccc 0 2

Sample Input 3

word sword drow words rows row

Sample Output 3

word sword drow words rows row

Explanation of Sample Test Cases

1. In Sample Input 1:

   • Transformations:
     • abc becomes abccba.
     • racecar is already a palindrome.
     • abba is already a palindrome.
     • car becomes carac.
     • abcba is already a palindrome.
     • ab becomes abba.
   • Compression:
     • The first occurrences of palindromes (abccba, racecar, abba, carac, abcba) are retained.
     • Subsequent occurrences (racecar, abba) are replaced by their first occurrence indices: 1 for racecar and 2 for abba.

2. In Sample Input 2:

   • Transformations:
     • aaa, bbb, and ccc are already palindromes.
   • Compression:
     • The first occurrences of palindromes (aaa, bbb, ccc) are retained.
     • Subsequent occurrences (aaa, ccc) are replaced by their first occurrence indices.

3. In Sample Input 3:

• All strings are unique palindromes after transformation, so no compression is needed.

import java.util.*;

public class PalindromeChainTransformer {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        String[] words = input.split(" ");
        
        Map<String, Integer> palindromeIndexMap = new HashMap<>();
        List<String> result = new ArrayList<>();
        
        for (String word : words) {
            String palindrome = makePalindrome(word);
            if (!palindromeIndexMap.containsKey(palindrome)) {
                palindromeIndexMap.put(palindrome, result.size());
                result.add(palindrome);
            } else {
                result.add(String.valueOf(palindromeIndexMap.get(palindrome)));
            }
        }
        
        System.out.println(String.join(" ", result));
        scanner.close();
    }
    
    private static String makePalindrome(String str) {
        if (isPalindrome(str)) {
            return str;
        }
        StringBuilder sb = new StringBuilder(str);
        for (int i = 0; i < str.length(); i++) {
            if (isPalindrome(str.substring(i))) {
                sb.append(new StringBuilder(str.substring(0, i)).reverse());
                break;
            }
        }
        return sb.toString();
    }
    
    private static boolean isPalindrome(String str) {
        int left = 0, right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

Insights
Palindrome Construction Logic: The makePalindrome function transforms strings into palindromes by appending the minimum characters required at the end.
Efficient Palindrome Detection: The isPalindrome method efficiently verifies if a string is a palindrome using a two-pointer approach, avoiding unnecessary string reversals.
Duplicate Handling with Map: A HashMap tracks the first occurrence of each unique palindrome, enabling compression by replacing duplicates with their indices.
Output Compression: The "Palindrome Chain Representation" reduces output size by mixing unique palindromes and indices of repeated values.
Handles Edge Cases: The program naturally handles edge cases such as already-palindromic strings, single-character strings, and empty inputs.
Time Complexity: With a complexity of O(n⋅m2)where nis the number of strings and m is the average string length, the program is efficient for moderate datasets.
Space Optimization: Unique palindromes are stored in the map, while duplicates are replaced with indices, optimizing memory usage.
Code Modularity: The division of logic into makePalindrome and isPalindrome functions enhances clarity, maintainability, and potential reuse.
User-Friendly Input Format: Accepting space-separated strings as input ensures compatibility with competitive programming scenarios.
Scalability Challenges: The O(m2) substring operations in makePalindrome may impact performance for large datasets, suggesting room for optimization.
"Don't just append to your code—make sure it's a pal-in-drome! Always write code that’s reversible, reusable, and just as smooth backward as forward!" 😄