String Manipulation Patterns — Loop Concatenation OOM

package io.thecodeforge.algo;

import java.util.Arrays;

public class StringWorkedExamples {

    /**
     * Reverses the order of words in a string.
     * Handles multiple spaces between words.
     */
    public static String reverseWords(String s) {
        // Split on whitespace, trim leading/trailing spaces first
        String[] words = s.trim().split("\\s+");

        // Reverse in-place using two pointers
        int left = 0, right = words.length - 1;
        while (left < right) {
            String temp = words[left];
            words[left] = words[right];
            words[right] = temp;
            left++;
            right--;
        }

        // Join with single space — never concatenate in a loop
        return String.join(" ", words);
    }

    /**
     * Checks if a string is a palindrome (alphanumeric only, case-insensitive).
     */
    public static boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    /**
     * Checks if two strings are anagrams using int[26] frequency map. O(n) time, O(1) space.
     */
    public static boolean areAnagrams(String s1, String s2) {
        if (s1.length() != s2.length()) return false;

        int[] freqint i = 0; i < s1.length(); = new int[26];
        for ( 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;
    }

    public static void main(String[] args) {
        System.out.println(reverseWords("  the sky  is  blue  ")); // "blue is sky the"
        System.out.println(isPalindrome("A man, a plan, a canal: Panama")); // true
        System.out.println(areAnagrams("listen", "silent")); // true
        System.out.println(areAnagrams("hello", "world")); // false
    }
}

package io.thecodeforge.algo;

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

public class StringPatterns {

    /**
     * Pattern 1: Frequency map 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[s1.charAt(i) - 'a']++;
            freq[s2.charAt(i) - 'a']--;
        }
        for (int count : freq) {
            if (count != 0) return false;
        }
        return true;
    }

    /**
     * Pattern 2: Two-pointer reverse. O(n) time, O(n) space (char array).
     */
    public static String reverseString(String s) {
        char[] chars = s.toCharArray();
        int left = 0, right = chars.length - 1;
        while (left < right) {
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            right--;
        }
        return new String(chars);
    }

    /**
     * Pattern 3: Sliding window — longest substring without repeating chars.
     */
    public static int longestUniqueSubstring(String s) {
        Map<Character, Integer> lastSeen = new HashMap<>();
        int maxLen = 0, windowStart = 0;
        for (int windowEnd = 0; windowEnd < s.length(); windowEnd++) {
            char ch = s.charAt(windowEnd);
            if (lastSeen.containsKey(ch)) {
                windowStart = Math.max(windowStart, lastSeen.get(ch));
            }
            lastSeen.put(ch, windowEnd + 1);
            maxLen = Math.max(maxLen, windowEnd - windowStart + 1);
        }
        return maxLen;
    }

    /**
     * Pattern 4: Build output with StringBuilder, join at end.
     */
    public static String reverseWords(String s) {
        String[] words = s.trim().split("\\s+");
        StringBuilder sb = new StringBuilder();
        for (int i = words.length - 1; i >= 0; i--) {
            sb.append(words[i]);
            if (i > 0) sb.append(' ');
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(areAnagrams("listen", "silent")); // true
        System.out.println(reverseString("hello")); // olleh
        System.out.println(longestUniqueSubstring("abcabcbb")); // 3
        System.out.println(reverseWords("  the sky  is  blue  ")); // "blue is sky the"
    }
}

package io.thecodeforge.algo;

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
    }
}

package io.thecodeforge.algo;

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

package io.thecodeforge.algo;

public class PalindromeChecker {

    /**
     * Checks if a string is a valid palindrome, considering only
     * alphanumeric characters and ignoring case.
     *
     * 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.
     *
     * 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++) {
            int oddLength = expandFromCenter(word, centerIndex, centerIndex);
            int evenLength = expandFromCenter(word, centerIndex, centerIndex + 1);
            int longerExpansion = Math.max(oddLength, evenLength);

            if (longerExpansion > bestLength) {
                bestLength = longerExpansion;
                bestStart = centerIndex - (longerExpansion - 1) / 2;
            }
        }

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

    private static int expandFromCenter(String word, int left, int right) {
        while (left >= 0 && right < word.length()
                && word.charAt(left) == word.charAt(right)) {
            left--;
            right++;
        }
        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"
    }
}

package io.thecodeforge.algo;

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.
     *
     * 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) {
        Map<String, List<String>> anagramBuckets = new HashMap<>();

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

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

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

    /**
     * Alternative fingerprint approach using a frequency-count key.
     * Avoids sorting entirely — O(n * k) overall.
     */
    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']++;
            }

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

package io.thecodeforge.algo;

public class StringBuilderBenchmark {

    /** Demonstrates the O(n^2) cost of string concatenation vs O(n) StringBuilder. */
    public static void main(String[] args) {
        int n = 100_000;

        // BAD: O(n^2) — each + copies all previous characters
        long start = System.nanoTime();
        String bad = "";
        for (int i = 0; i < n; i++) {
            bad += "a"; // new String object each iteration
        }
        long badTime = System.nanoTime() - start;

        // GOOD: O(n) — StringBuilder appends in-place
        start = System.nanoTime();
        StringBuilder sb = new StringBuilder(n); // pre-sized
        for (int i = 0; i < n; i++) {
            sb.append('a');
        }
        String good = sb.toString();
        long goodTime = System.nanoTime() - start;

        System.out.println("String +000)
StringBuilder:   1 ms (length=100000)
Speedup: 84 loop:  " + badTime / 1_000_000 + " ms (length=" + bad.length() + ")");
        System.out.println("StringBuilder:   " + goodTime / 1_000_000 + " ms (length=" + good.length() + ")");
        System.out.println("Speedup: " + (badTime / Math.max(goodTime, 1)) + "x");
    }
}

// io.thecodeforge — dsa tutorial

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd;
}

public class TrieAutocomplete {
    TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new TrieNode();
            }
            node = node.children[idx];
        }
        node.isEnd = true;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return false;
            node = node.children[idx];
        }
        return true;
    }

    public static void main(String[] args) {
        TrieAutocomplete t = new TrieAutocomplete();
        t.insert("codeforge");
        t.insert("codecrash");
        System.out.println(t.startsWith("code"));   // true
        System.out.println(t.startsWith("coda"));   // false
    }
}

// io.thecodeforge — dsa tutorial

public class RabinKarpSearch {
    private static final int BASE = 256;
    private static final int PRIME = 101;

    public static int search(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        if (m > n) return -1;

        long patternHash = 0, windowHash = 0, highestPower = 1;
        for (int i = 0; i < m - 1; i++) {
            highestPower = (highestPower * BASE) % PRIME;
        }

        for (int i = 0; i < m; i++) {
            patternHash = (patternHash * BASE + pattern.charAt(i)) % PRIME;
            windowHash = (windowHash * BASE + text.charAt(i)) % PRIME;
        }

        for (int i = 0; i <= n - m; i++) {
            if (patternHash == windowHash) {
                boolean match = true;
                for (int j = 0; j < m; j++) {
                    if (text.charAt(i + j) != pattern.charAt(j)) {
                        match = false;
                        break;
                    }
                }
                if (match) return i;
            }
            if (i < n - m) {
                windowHash = (BASE * (windowHash - text.charAt(i) * highestPower) 
                           + text.charAt(i + m)) % PRIME;
                if (windowHash < 0) windowHash += PRIME;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String text = "thecodeforgepatternhunt";
        String pattern = "pattern";
        System.out.println(search(text, pattern));  // 11
    }
}

// io.thecodeforge — dsa tutorial

import java.util.*;

public class CustomComparatorExample {
    public static void main(String[] args) {
        String[] words = {"apple", "fig", "banana", "kiwi", "grape"};
        
        // Sort by length ascending, then alphabetically for ties
        Arrays.sort(words, (a, b) -> {
            if (a.length() != b.length()) {
                return Integer.compare(a.length(), b.length());
            }
            return a.compareTo(b);
        });
        
        System.out.println(Arrays.toString(words));
    }
}

// io.thecodeforge — dsa tutorial

public class StringBuilderVsBuffer {
    public static void main(String[] args) {
        int n = 100_000;
        long start, end;
        
        // StringBuilder (fast)
        start = System.nanoTime();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append("a");
        }
        String result = sb.toString();
        end = System.nanoTime();
        System.out.println("StringBuilder: " + (end - start) / 1_000_000 + " ms");
        
        // StringBuffer (slow — pays for locks)
        start = System.nanoTime();
        StringBuffer sbf = new StringBuffer();
        for (int i = 0; i < n; i++) {
            sbf.append("a");
        }
        result = sbf.toString();
        end = System.nanoTime();
        System.out.println("StringBuffer: " + (end - start) / 1_000_000 + " ms");
    }
}

// io.thecodeforge — dsa tutorial

import java.util.ArrayDeque;
import java.util.Deque;

public class NextGreaterChar {
    public int[] nextGreater(String s) {
        int n = s.length();
        int[] res = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && s.charAt(i) > s.charAt(stack.peek())) {
                res[stack.pop()] = i;
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) res[stack.pop()] = -1;
        return res;
    }
}

// io.thecodeforge — dsa tutorial

public class URLify {
    public void replaceSpaces(char[] str, int trueLength) {
        int spaceCount = 0;
        for (int i = 0; i < trueLength; i++) if (str[i] == ' ') spaceCount++;
        int index = trueLength + spaceCount * 2;
        for (int i = trueLength - 1; i >= 0; i--) {
            if (str[i] == ' ') {
                str[--index] = '0';
                str[--index] = '2';
                str[--index] = '%';
            } else str[--index] = str[i];
        }
    }
}

// io.thecodeforge — dsa tutorial

import java.util.*;

public class Permutations {
    public List<String> permute(String s) {
        List<String> res = new ArrayList<>();
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        backtrack(chars, new boolean[chars.length], new StringBuilder(), res);
        return res;
    }
    private void backtrack(char[] chars, boolean[] used, StringBuilder path, List<String> res) {
        if (path.length() == chars.length) {
            res.add(path.toString());
            return;
        }
        for (int i = 0; i < chars.length; i++) {
            if (used[i] || (i > 0 && chars[i] == chars[i-1] && !used[i-1])) continue;
            used[i] = true;
            path.append(chars[i]);
            backtrack(chars, used, path, res);
            path.deleteCharAt(path.length() - 1);
            used[i] = false;
        }
    }
}