String Manipulation Patterns in DSA — The Definitive Guide

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

public class LongestUniqueSubstring {

    /**
     * Finds the length of the longest substring without repeating characters.
     * Classic variable-size sliding window problem.
     *
     * Time:  O(n) — each character is visited at most twice (once by right, once by left)
     * Space: O(min(n, alphabet)) — the map holds at most one entry per unique character
     */
    public static int findLongestUniqueSubstring(String input) {
        // Maps each character to the index AFTER its last known position.
        // Storing index+1 lets us jump the left pointer forward in one step.
        Map<Character, Integer> lastSeenAt = new HashMap<>();

        int maxLength = 0;
        int windowStart = 0; // left edge of our sliding window

        for (int windowEnd = 0; windowEnd < input.length(); windowEnd++) {
            char currentChar = input.charAt(windowEnd);

            // If this character already exists inside our current window,
            // move the left edge just past its previous position so the
            // window no longer contains the duplicate.
            if (lastSeenAt.containsKey(currentChar)) {
                // Math.max prevents the window from moving BACKWARD
                // if the duplicate was outside the current window.
                windowStart = Math.max(windowStart, lastSeenAt.get(currentChar));
            }

            // Record this character's "next safe position" for the left pointer
            lastSeenAt.put(currentChar, windowEnd + 1);

            // Current window length = windowEnd - windowStart + 1
            maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        System.out.println(findLongestUniqueSubstring("abcabcbb"));  // 3  → "abc"
        System.out.println(findLongestUniqueSubstring("bbbbb"));     // 1  → "b"
        System.out.println(findLongestUniqueSubstring("pwwkew"));    // 3  → "wke"
        System.out.println(findLongestUniqueSubstring(""));          // 0  → empty string
        System.out.println(findLongestUniqueSubstring("abcdefg"));   // 7  → whole string
    }
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class AnagramFinder {

    /**
     * Returns all starting indices where an anagram of 'pattern' begins in 'text'.
     * Uses a fixed-size sliding window with an int[26] frequency map.
     *
     * Time:  O(n) where n = text.length()
     * Space: O(1) — the two int[26] arrays are constant size regardless of input
     */
    public static List<Integer> findAnagramStartIndices(String text, String pattern) {
        List<Integer> resultIndices = new ArrayList<>();

        // Edge case: pattern can't fit inside text
        if (pattern.length() > text.length()) {
            return resultIndices;
        }

        int windowSize = pattern.length();

        // Build the frequency fingerprint for the target pattern
        int[] patternFrequency = new int[26];
        for (char ch : pattern.toCharArray()) {
            patternFrequency[ch - 'a']++; // 'a'=0, 'b'=1, ..., 'z'=25
        }

        // Build the frequency fingerprint for the first window in text
        int[] windowFrequency = new int[26];
        for (int i = 0; i < windowSize; i++) {
            windowFrequency[text.charAt(i) - 'a']++;
        }

        // Check the first window before we start sliding
        if (Arrays.equals(patternFrequency, windowFrequency)) {
            resultIndices.add(0);
        }

        // Slide the window one character at a time
        for (int windowEnd = windowSize; windowEnd < text.length(); windowEnd++) {
            // Add the new character entering the right side of the window
            windowFrequency[text.charAt(windowEnd) - 'a']++;

            // Remove the character leaving the left side of the window
            int windowStart = windowEnd - windowSize;
            windowFrequency[text.charAt(windowStart) - 'a']--;

            // Arrays.equals on two int[26] arrays is 26 comparisons — O(1)
            if (Arrays.equals(patternFrequency, windowFrequency)) {
                resultIndices.add(windowStart + 1); // +1 because new window starts one ahead
            }
        }

        return resultIndices;
    }

    public static void main(String[] args) {
        System.out.println(findAnagramStartIndices("cbaebabacd", "abc")); // [0, 6]
        System.out.println(findAnagramStartIndices("abab", "ab"));        // [0, 1, 2]
        System.out.println(findAnagramStartIndices("af", "be"));          // []
    }
}

public class PalindromeChecker {

    /**
     * Checks if a string is a valid palindrome, considering only
     * alphanumeric characters and ignoring case.
     * Real-world variant of the classic problem — matches how
     * "A man, a plan, a canal: Panama" is considered a palindrome.
     *
     * Time:  O(n)
     * Space: O(1) — no extra data structures, just two integer pointers
     */
    public static boolean isValidPalindrome(String sentence) {
        int leftPointer = 0;
        int rightPointer = sentence.length() - 1;

        while (leftPointer < rightPointer) {
            // Skip non-alphanumeric characters from the left
            while (leftPointer < rightPointer
                    && !Character.isLetterOrDigit(sentence.charAt(leftPointer))) {
                leftPointer++;
            }

            // Skip non-alphanumeric characters from the right
            while (leftPointer < rightPointer
                    && !Character.isLetterOrDigit(sentence.charAt(rightPointer))) {
                rightPointer--;
            }

            // Compare characters at both pointers, case-insensitive
            char leftChar  = Character.toLowerCase(sentence.charAt(leftPointer));
            char rightChar = Character.toLowerCase(sentence.charAt(rightPointer));

            if (leftChar != rightChar) {
                return false; // Mismatch — definitely not a palindrome
            }

            // Both characters matched — move both pointers inward
            leftPointer++;
            rightPointer--;
        }

        // All mirrored pairs matched
        return true;
    }

    /**
     * Finds the length of the longest palindromic substring using
     * the "expand around center" technique — a two-pointer expansion.
     * Handles both odd-length ("racecar") and even-length ("abba") palindromes.
     *
     * Time:  O(n²) — each of the 2n-1 centers expands up to n/2 times
     * Space: O(1)
     */
    public static String longestPalindromicSubstring(String word) {
        if (word == null || word.isEmpty()) return "";

        int bestStart  = 0;
        int bestLength = 1;

        for (int centerIndex = 0; centerIndex < word.length(); centerIndex++) {
            // Expand for ODD-length palindromes (single character center)
            int oddLength = expandFromCenter(word, centerIndex, centerIndex);

            // Expand for EVEN-length palindromes (gap between two characters)
            int evenLength = expandFromCenter(word, centerIndex, centerIndex + 1);

            int longerExpansion = Math.max(oddLength, evenLength);

            if (longerExpansion > bestLength) {
                bestLength = longerExpansion;
                // Reverse-calculate where this palindrome starts
                bestStart = centerIndex - (longerExpansion - 1) / 2;
            }
        }

        return word.substring(bestStart, bestStart + bestLength);
    }

    private static int expandFromCenter(String word, int left, int right) {
        // Keep expanding outward while characters match and we're in bounds
        while (left >= 0 && right < word.length()
                && word.charAt(left) == word.charAt(right)) {
            left--;
            right++;
        }
        // When the loop exits, left and right have gone one step too far
        // Length formula: right - left - 1
        return right - left - 1;
    }

    public static void main(String[] args) {
        System.out.println(isValidPalindrome("A man, a plan, a canal: Panama")); // true
        System.out.println(isValidPalindrome("race a car"));                      // false
        System.out.println(isValidPalindrome(" "));                               // true

        System.out.println(longestPalindromicSubstring("babad"));   // "bab" or "aba"
        System.out.println(longestPalindromicSubstring("cbbd"));    // "bb"
        System.out.println(longestPalindromicSubstring("racecar")); // "racecar"
    }
}

import java.util.*;

public class AnagramGrouper {

    /**
     * Groups a list of words so that anagrams appear together.
     * Uses a sorted-character string as a canonical hash key.
     *
     * Real-world use: autocorrect dictionaries, scrabble solvers,
     * duplicate content detection in CMS platforms.
     *
     * Time:  O(n * k log k) where n = number of words, k = average word length
     * Space: O(n * k) to store all words in the result map
     */
    public static List<List<String>> groupAnagrams(String[] words) {
        // Key: sorted characters of a word (its anagram fingerprint)
        // Value: all words that share that fingerprint
        Map<String, List<String>> anagramBuckets = new HashMap<>();

        for (String word : words) {
            // Sort the characters to create a canonical key
            // "eat", "tea", "ate" all produce "aet"
            char[] wordChars = word.toCharArray();
            Arrays.sort(wordChars);
            String canonicalKey = new String(wordChars);

            // computeIfAbsent creates a new list only when the key is new
            anagramBuckets.computeIfAbsent(canonicalKey, k -> new ArrayList<>()).add(word);
        }

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

    /**
     * Alternative fingerprint approach using a frequency-count key.
     * Avoids sorting entirely — O(n * k) overall.
     * Useful when k is large (long words) and sorting becomes the bottleneck.
     */
    public static List<List<String>> groupAnagramsLinear(String[] words) {
        Map<String, List<String>> anagramBuckets = new HashMap<>();

        for (String word : words) {
            int[] charCounts = new int[26];
            for (char ch : word.toCharArray()) {
                charCounts[ch - 'a']++;
            }

            // Build a string like "#2#0#1#..." to represent the frequency map
            // This string uniquely identifies an anagram family
            StringBuilder keyBuilder = new StringBuilder();
            for (int count : charCounts) {
                keyBuilder.append('#').append(count);
            }
            String frequencyKey = keyBuilder.toString();

            anagramBuckets.computeIfAbsent(frequencyKey, k -> new ArrayList<>()).add(word);
        }

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

    public static void main(String[] args) {
        String[] wordList = {"eat", "tea", "tan", "ate", "nat", "bat"};

        List<List<String>> grouped = groupAnagrams(wordList);
        System.out.println("Sorted-key approach:");
        for (List<String> group : grouped) {
            System.out.println("  " + group);
        }

        System.out.println("\nFrequency-key approach:");
        List<List<String>> groupedLinear = groupAnagramsLinear(wordList);
        for (List<String> group : groupedLinear) {
            System.out.println("  " + group);
        }
    }
}