Anagram and Palindrome Problems Explained — Java DSA Guide for Beginners

package io.thecodeforge.algo;

import java.util.*;

public class StringWorkedExamples {

    /**
     * Groups words by anagram families using sorted-character keys.
     */
    public static List<List<String>> groupAnagrams(String[] words) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String word : words) {
            char[] chars = word.toLowerCase().toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(word);
        }
        return new ArrayList<>(groups.values());
    }

    /**
     * Checks if a string is a palindrome
    public static boolean isPalindrome(String s) {\ (alphanumeric only, case-insensitive).
     */n        String cleaned = s.toLowerCase().replaceAll("[^a-z0-9]", "");
        int left = 0, right = cleaned.length() - 1;
        while (left < right) {
            if (cleaned.charAt(left) != cleaned.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        String[] words = {"eat", "tea", "tan", "ate", "nat", "bat"};
        System.out.println("Groups: " + groupAnagrams(words));
        System.out.println("Palindrome: " + isPalindrome("A man a plan a canal Panama"));
    }
}

package io.thecodeforge.algo;

public class AnagramPalindromePlain {

    /** Anagram check: O(n) time, O(1) space. */
    public static boolean areAnagrams(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        int[] freq = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            freq[Character.toLowerCase(s1.charAt(i)) - 'a']++;
            freq[Character.toLowerCase(s2.charAt(i)) - 'a']--;
        }
        for (int count : freq) {
            if (count != 0) return false;
        }
        return true;
    }

    /** Palindrome check: O(n) time, O(1) space. */
    public static boolean isPalindrome(String s) {
        String cleaned = s.toLowerCase().replaceAll("[^a-z0-9]", "");
        int left = 0, right = cleaned.length() - 1;
        while (left < right) {
            if (cleaned.charAt(left) != cleaned.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(areAnagrams("listen", "silent")); // true
        System.out.println(isPalindrome("racecar"));          // true
    }
}

package io.thecodeforge.algo;

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
        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
        if (cleanFirst.length() != cleanSecond.length()) {
            return false;
        }

        // Step 3: Create a frequency array — 26 slots, one per letter a-z
        int[] letterFrequency = new int[26];

        // Step 4: Walk through the first word, incrementing the count
        for (char letter : cleanFirst.toCharArray()) {
            letterFrequency[letter - 'a']++;
        }

        // Step 5: Walk through the second word, DECREMENTING the count
        for (char letter : cleanSecond.toCharArray()) {
            letterFrequency[letter - 'a']--;
        }

        // Step 6: If every slot is exactly zero, the frequencies matched perfectly
        for (int frequency : letterFrequency) {
            if (frequency != 0) {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        System.out.println(areAnagrams("listen", "silent"));          // true
        System.out.println(areAnagrams("Astronomer", "Moon starer")); // true
        System.out.println(areAnagrams("cat", "car"));                // false
        System.out.println(areAnagrams("hello", "helloo"));           // false
        System.out.println(areAnagrams("a", "a"));                    // true
    }
}

package io.thecodeforge.algo;

public class PalindromeChecker {

    /**
     * Checks if a string is a valid palindrome using the two-pointer technique.
     * Ignores spaces and case.
     *
     * Time Complexity:  O(n) — each character is visited at most once
     * Space Complexity: O(1) — only two integer pointers
     */
    public static boolean isPalindrome(String inputText) {
        String cleanedText = inputText.toLowerCase().replaceAll("[^a-z0-9]", "");

        if (cleanedText.length() <= 1) {
            return true;
        }

        int leftIndex  = 0;
        int rightIndex = cleanedText.length() - 1;

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

            if (leftChar != rightChar) {
                return false;
            }

            leftIndex++;
            rightIndex--;
        }

        return true;
    }

    public static void main(String[] args) {
        System.out.println(isPalindrome("racecar"));                     // true
        System.out.println(isPalindrome("abba"));                        // true
        System.out.println(isPalindrome("A man a plan a canal Panama")); // true
        System.out.println(isPalindrome("hello"));                       // false
        System.out.println(isPalindrome("z"));                           // true
    }
}

package io.thecodeforge.algo;

import java.util.*;

public class AdvancedStringProblems {

    public static List<List<String>> groupAnagrams(String[] words) {
        Map<String, List<String>> anagramGroups = new HashMap<>();

        for (String word : words) {
            char[] wordCharacters = word.toCharArray();
            Arrays.sort(wordCharacters);
            String sortedKey = new String(wordCharacters);

            anagramGroups.computeIfAbsent(sortedKey, k -> new ArrayList<>()).add(word);
        }

        return new ArrayList<>(anagramGroups.values());
    }

    public static String longestPalindromicSubstring(String inputText) {
        if (inputText == null || inputText.length() < 1) return "";

        int longestStart  = 0;
        int longestEnd    = 0;

        for (int centreIndex = 0; centreIndex < inputText.length(); centreIndex++) {
            int oddLength = expandFromCentre(inputText, centreIndex, centreIndex);
            int evenLength = expandFromCentre(inputText, centreIndex, centreIndex + 1);
            int maxLengthAtThisCentre = Math.max(oddLength, evenLength);

            if (maxLengthAtThisCentre > longestEnd - longestStart + 1) {
                longestStart = centreIndex - (maxLengthAtThisCentre - 1) / 2;
                longestEnd   = centreIndex + maxLengthAtThisCentre / 2;
            }
        }

        return inputText.substring(longestStart, longestEnd + 1);
    }

    private static int expandFromCentre(String text, int leftPointer, int rightPointer) {
        while (leftPointer >= 0
                && rightPointer < text.length()
                && text.charAt(leftPointer) == text.charAt(rightPointer)) {
            leftPointer--;
            rightPointer++;
        }
        return rightPointer - leftPointer - 1;
    }

    public static void main(String[] args) {
        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();

        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"));
    }
}

package io.thecodeforge.algo;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class FrequencyCounterBenchmark {

    /** int[26] anagram check: O(n) time, O(1) space. */
    public static boolean anagramWithArray(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        int[] freq = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            freq[s1.charAt(i) - 'a']++;
            freq[s2.charAt(i) - 'a']--;
        }
        for (int count : freq) {
            if (count != 0) return false;
        }
        return true;
    }

    /** HashMap anagram check: O(n) time, O(k) space where k = unique chars. */
    public static boolean anagramWithMap(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s1.toCharArray()) {
            freq.merge(c, 1, Integer::sum);
        }
        for (char c : s2.toCharArray()) {
            freq.merge(c, -1, Integer::sum);
            if (freq.get(c) == 0) freq.remove(c);
        }
        return freq.isEmpty();
    }

    public static void main(String[] args) {
        // Generate a long test string
        StringBuilder sb = new StringBuilder(1_000_000);
        for (int i = 0; i < 1_000_000; i++) {
            sb.append((char) ('a' + (i % 26)));
        }
        String s1 = sb.toString();
        String s2 = new StringBuilder(s1).reverse().toString();

        // Benchmark int[26]
        long start = System.nanoTime();
        for (int i = 0; i < 100; i++) {
            anagramWithArray(s1, s2);
        }
        long arrayTime = System.nanoTime() - start;

        // Benchmark HashMap
        start = System.nanoTime();
        for (int i = 0; i < 100; i++) {
            anagramWithMap(s1, s2);
        }
        long mapTime = System.nanoTime() - start;

        System.out.println("int[26]:  " + arrayTime / 1_000_000 + " ms");
        System.out.println("HashMap:  " + mapTime / 1_000_000 + " ms");
        System.out.println("Speedup:  " + (mapTime / Math.max(arrayTime, 1)) + "x");
    }
}