Anagram and Palindrome Problems Explained — Java DSA Guide for Beginners

public class AnagramChecker {

    /**
     * Checks if two strings are anagrams of each other.
     * Ignores case, ignores spaces — just like real word puzzles.
     *
     * Time Complexity:  O(n) — we scan each string once
     * Space Complexity: O(1) — fixed-size array of 26, regardless of input size
     */
    public static boolean areAnagrams(String firstWord, String secondWord) {

        // Step 1: Normalise both strings — lowercase, no spaces
        // This means "Listen" and "Silent" will still match
        String cleanFirst  = firstWord.toLowerCase().replaceAll("\\s", "");
        String cleanSecond = secondWord.toLowerCase().replaceAll("\\s", "");

        // Step 2: Quick sanity check — if lengths differ after cleaning,
        // they can't possibly be anagrams (different total character counts)
        if (cleanFirst.length() != cleanSecond.length()) {
            return false;
        }

        // Step 3: Create a frequency array — 26 slots, one per letter a-z
        // All slots start at 0 by default in Java
        int[] letterFrequency = new int[26];

        // Step 4: Walk through the first word, incrementing the count
        // for each character we encounter.
        // 'a' has ASCII value 97. Subtracting 'a' maps 'a'->0, 'b'->1, etc.
        for (char letter : cleanFirst.toCharArray()) {
            letterFrequency[letter - 'a']++;
        }

        // Step 5: Walk through the second word, DECREMENTING the count.
        // If the second word has a letter not in the first, its slot goes negative.
        for (char letter : cleanSecond.toCharArray()) {
            letterFrequency[letter - 'a']--;
        }

        // Step 6: If every slot is exactly zero, the frequencies matched perfectly.
        // Any non-zero slot means one word had more of some letter than the other.
        for (int frequency : letterFrequency) {
            if (frequency != 0) {
                return false; // Mismatch found — not an anagram
            }
        }

        return true; // All frequencies balanced out — they ARE anagrams!
    }

    public static void main(String[] args) {

        // Test case 1: Classic anagram pair
        System.out.println(areAnagrams("listen", "silent"));       // true

        // Test case 2: Anagram with mixed case
        System.out.println(areAnagrams("Astronomer", "Moon starer")); // true

        // Test case 3: Not an anagram — 't' vs 'r'
        System.out.println(areAnagrams("cat", "car"));              // false

        // Test case 4: Different lengths
        System.out.println(areAnagrams("hello", "helloo"));         // false

        // Test case 5: Single characters that match
        System.out.println(areAnagrams("a", "a"));                  // true
    }
}

public class PalindromeChecker {

    /**
     * Checks if a string is a palindrome using the two-pointer technique.
     * Ignores spaces and case so real phrases like "Race a car" work correctly.
     *
     * Time Complexity:  O(n) — each character is visited at most once
     * Space Complexity: O(n) — only for the cleaned string; logic itself is O(1)
     */
    public static boolean isPalindrome(String inputText) {

        // Step 1: Clean the input — remove spaces, make lowercase
        // We want "A man a plan a canal Panama" to return true
        String cleanedText = inputText.toLowerCase().replaceAll("[^a-z0-9]", "");

        // Step 2: Edge case — an empty string or single character is always a palindrome
        if (cleanedText.length() <= 1) {
            return true;
        }

        // Step 3: Set up two pointers — one at each end of the string
        int leftIndex  = 0;
        int rightIndex = cleanedText.length() - 1;

        // Step 4: March the pointers toward the centre
        // They stop when they meet (odd length) or cross (even length)
        while (leftIndex < rightIndex) {

            char leftChar  = cleanedText.charAt(leftIndex);
            char rightChar = cleanedText.charAt(rightIndex);

            // Step 5: If the characters don't match — it's NOT a palindrome.
            // We can exit immediately, no need to check further.
            if (leftChar != rightChar) {
                return false;
            }

            // Step 6: Characters matched — move both pointers one step inward
            leftIndex++;
            rightIndex--;
        }

        // Step 7: If we made it through the whole loop without returning false,
        // every mirrored pair matched — it IS a palindrome!
        return true;
    }

    /**
     * BONUS: Check if a string is a palindrome by comparing it to its reverse.
     * Simpler to read, but uses O(n) extra space for the reversed string.
     * Great to mention in an interview as the naive approach before optimising.
     */
    public static boolean isPalindromeNaive(String inputText) {
        String cleanedText = inputText.toLowerCase().replaceAll("[^a-z0-9]", "");
        String reversedText = new StringBuilder(cleanedText).reverse().toString();
        // Direct string comparison — true only if they're identical
        return cleanedText.equals(reversedText);
    }

    public static void main(String[] args) {

        // Test case 1: Classic odd-length palindrome
        System.out.println(isPalindrome("racecar"));                         // true

        // Test case 2: Classic even-length palindrome
        System.out.println(isPalindrome("abba"));                            // true

        // Test case 3: Famous phrase palindrome (spaces and mixed case ignored)
        System.out.println(isPalindrome("A man a plan a canal Panama"));     // true

        // Test case 4: Not a palindrome
        System.out.println(isPalindrome("hello"));                           // false

        // Test case 5: Single character
        System.out.println(isPalindrome("z"));                               // true

        // Test case 6: Naive approach for comparison
        System.out.println(isPalindromeNaive("Madam"));                      // true
    }
}

import java.util.*;

public class AdvancedStringProblems {

    // ─────────────────────────────────────────────────────────────
    // PROBLEM 1: Group Anagrams
    // Input:  ["eat", "tea", "tan", "ate", "nat", "bat"]
    // Output: [["eat","tea","ate"], ["tan","nat"], ["bat"]]
    // ─────────────────────────────────────────────────────────────

    public static List<List<String>> groupAnagrams(String[] words) {

        // A HashMap where:
        //   key   = the sorted version of a word (e.g. "aet" for "eat","tea","ate")
        //   value = the list of original words that sort to that key
        Map<String, List<String>> anagramGroups = new HashMap<>();

        for (String word : words) {

            // Sort the characters of the word to create a canonical key
            // "eat" -> char array ['e','a','t'] -> sorted ['a','e','t'] -> "aet"
            char[] wordCharacters = word.toCharArray();
            Arrays.sort(wordCharacters);
            String sortedKey = new String(wordCharacters);

            // If this key doesn't exist in the map yet, create a new list for it
            // computeIfAbsent is cleaner than a manual if-null check
            anagramGroups.computeIfAbsent(sortedKey, k -> new ArrayList<>());

            // Add the original word to its anagram group
            anagramGroups.get(sortedKey).add(word);
        }

        // Return all the groups as a list of lists
        return new ArrayList<>(anagramGroups.values());
    }

    // ─────────────────────────────────────────────────────────────
    // PROBLEM 2: Longest Palindromic Substring
    // Input:  "babad"
    // Output: "bab" (or "aba" — both are valid)
    //
    // Input:  "cbbd"
    // Output: "bb"
    // ─────────────────────────────────────────────────────────────

    public static String longestPalindromicSubstring(String inputText) {

        if (inputText == null || inputText.length() < 1) return "";

        // Track the start and end indices of the longest palindrome found
        int longestStart  = 0;
        int longestEnd    = 0;

        for (int centreIndex = 0; centreIndex < inputText.length(); centreIndex++) {

            // Case 1: Odd-length palindromes (single character centre)
            // e.g. "racecar" — centre is 'e'
            int oddLength = expandFromCentre(inputText, centreIndex, centreIndex);

            // Case 2: Even-length palindromes (gap between two characters as centre)
            // e.g. "abba" — centre is the gap between the two b's
            int evenLength = expandFromCentre(inputText, centreIndex, centreIndex + 1);

            // Take whichever expansion was longer
            int maxLengthAtThisCentre = Math.max(oddLength, evenLength);

            // Check if this is longer than the best we've found so far
            if (maxLengthAtThisCentre > longestEnd - longestStart + 1) {
                // Back-calculate the start and end indices from the length
                // (integer division handles both odd and even lengths correctly)
                longestStart = centreIndex - (maxLengthAtThisCentre - 1) / 2;
                longestEnd   = centreIndex + maxLengthAtThisCentre / 2;
            }
        }

        // Extract and return the actual substring
        return inputText.substring(longestStart, longestEnd + 1);
    }

    /**
     * Helper: Expands outward from a centre position as long as characters match.
     * Returns the LENGTH of the palindrome found.
     *
     * For odd palindromes:  call with (index, index)
     * For even palindromes: call with (index, index + 1)
     */
    private static int expandFromCentre(String text, int leftPointer, int rightPointer) {
        // Expand outward while within bounds AND characters still match
        while (leftPointer >= 0
                && rightPointer < text.length()
                && text.charAt(leftPointer) == text.charAt(rightPointer)) {
            leftPointer--;   // Move left pointer further left
            rightPointer++;  // Move right pointer further right
        }
        // When the loop ends, pointers have gone ONE step too far.
        // The actual palindrome length is rightPointer - leftPointer - 1.
        return rightPointer - leftPointer - 1;
    }

    public static void main(String[] args) {

        // ── Group Anagrams Demo ──
        String[] wordList = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> groups = groupAnagrams(wordList);
        System.out.println("Anagram Groups:");
        for (List<String> group : groups) {
            System.out.println("  " + group);
        }

        System.out.println();

        // ── Longest Palindromic Substring Demo ──
        System.out.println("Longest palindrome in 'babad':  " + longestPalindromicSubstring("babad"));
        System.out.println("Longest palindrome in 'cbbd':   " + longestPalindromicSubstring("cbbd"));
        System.out.println("Longest palindrome in 'racecar': " + longestPalindromicSubstring("racecar"));
        System.out.println("Longest palindrome in 'abacaba': " + longestPalindromicSubstring("abacaba"));
    }
}