import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/** 30 Java String programs for interviews: brute force, optimal, and (where it makes sense) a stream version.
 *  Run with: java StringInterviewPrograms.java */
public class StringInterviewPrograms {

    // ---------- reporting helpers ----------
    static void rep(int n, String title, Object brute, Object opt, Object stream) {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("P%02d %s -> brute=%s | optimal=%s", n, title, brute, opt));
        boolean same = Objects.equals(brute, opt);
        if (stream != null) {
            sb.append(" | stream=").append(stream);
            same &= Objects.equals(opt, stream);
        }
        sb.append(" | same=").append(same);
        System.out.println(sb);
    }

    static void one(int n, String title, Object result) {
        System.out.printf("P%02d %s -> %s%n", n, title, result);
    }

    // ---------- P01 reverse a string ----------
    static String reverseBrute(String s) {
        String r = "";
        for (int i = s.length() - 1; i >= 0; i--) r += s.charAt(i);
        return r;
    }

    static String reverseOpt(String s) {
        return new StringBuilder(s).reverse().toString();
    }

    static String reverseStream(String s) {
        return IntStream.range(0, s.length()).mapToObj(i -> String.valueOf(s.charAt(s.length() - 1 - i)))
                .collect(Collectors.joining());
    }

    // ---------- P02 palindrome ----------
    static boolean palBrute(String s) {
        return s.equals(reverseOpt(s));
    }

    static boolean palOpt(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) if (s.charAt(i++) != s.charAt(j--)) return false;
        return true;
    }

    static boolean palStream(String s) {
        return IntStream.range(0, s.length() / 2).allMatch(i -> s.charAt(i) == s.charAt(s.length() - 1 - i));
    }

    static String clean(String s) {
        return s.toLowerCase().replaceAll("[^a-z0-9]", "");
    }

    // ---------- P03 vowels and consonants ----------
    static String vcBrute(String s) {
        int v = 0, c = 0;
        for (char ch : s.toCharArray()) {
            if (Character.isLetter(ch)) {
                if ("aeiouAEIOU".indexOf(ch) >= 0) v++;
                else c++;
            }
        }
        return v + "/" + c;
    }

    static String vcOpt(String s) {
        int v = 0, c = 0;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (!Character.isLetter(ch)) continue;
            switch (Character.toLowerCase(ch)) {
                case 'a', 'e', 'i', 'o', 'u' -> v++;
                default -> c++;
            }
        }
        return v + "/" + c;
    }

    static String vcStream(String s) {
        long v = s.chars().filter(ch -> "aeiouAEIOU".indexOf(ch) >= 0).count();
        long c = s.chars().filter(Character::isLetter).count() - v;
        return v + "/" + c;
    }

    // ---------- P04 character frequency ----------
    static Map<Character, Integer> freqBrute(String s) {
        Map<Character, Integer> m = new TreeMap<>();
        for (char c : s.toCharArray()) {
            if (m.containsKey(c)) m.put(c, m.get(c) + 1);
            else m.put(c, 1);
        }
        return m;
    }

    static Map<Character, Integer> freqOpt(String s) {
        int[] cnt = new int[128];
        for (char c : s.toCharArray()) cnt[c]++;
        Map<Character, Integer> m = new TreeMap<>();
        for (char c = 0; c < 128; c++) if (cnt[c] > 0) m.put(c, cnt[c]);
        return m;
    }

    static Map<Character, Integer> freqStream(String s) {
        return s.chars().mapToObj(c -> (char) c).collect(Collectors.groupingBy(Function.identity(), TreeMap::new,
                Collectors.collectingAndThen(Collectors.counting(), Long::intValue)));
    }

    // ---------- P05 first non-repeated character ----------
    static Character fnrBrute(String s) {
        for (int i = 0; i < s.length(); i++) {
            boolean dup = false;
            for (int j = 0; j < s.length(); j++) {
                if (i != j && s.charAt(i) == s.charAt(j)) { dup = true; break; }
            }
            if (!dup) return s.charAt(i);
        }
        return null;
    }

    static Character fnrOpt(String s) {
        int[] c = new int[65536];
        for (char ch : s.toCharArray()) c[ch]++;
        for (char ch : s.toCharArray()) if (c[ch] == 1) return ch;
        return null;
    }

    static Character fnrStream(String s) {
        return s.chars().mapToObj(x -> (char) x)
                .collect(Collectors.groupingBy(Function.identity(), LinkedHashMap::new, Collectors.counting()))
                .entrySet().stream().filter(e -> e.getValue() == 1).map(Map.Entry::getKey).findFirst().orElse(null);
    }

    // ---------- P06 first repeated character ----------
    static Character frBrute(String s) {
        for (int j = 1; j < s.length(); j++) if (s.substring(0, j).indexOf(s.charAt(j)) >= 0) return s.charAt(j);
        return null;
    }

    static Character frOpt(String s) {
        Set<Character> seen = new HashSet<>();
        for (char c : s.toCharArray()) if (!seen.add(c)) return c;
        return null;
    }

    // ---------- P07 remove duplicate characters ----------
    static String dedupBrute(String s) {
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) if (sb.indexOf(String.valueOf(c)) < 0) sb.append(c);
        return sb.toString();
    }

    static String dedupOpt(String s) {
        Set<Character> set = new LinkedHashSet<>();
        for (char c : s.toCharArray()) set.add(c);
        StringBuilder sb = new StringBuilder();
        for (char c : set) sb.append(c);
        return sb.toString();
    }

    static String dedupStream(String s) {
        return s.chars().distinct().mapToObj(c -> String.valueOf((char) c)).collect(Collectors.joining());
    }

    // ---------- P08 anagram ----------
    static boolean anaSort(String a, String b) {
        char[] x = a.toCharArray(), y = b.toCharArray();
        Arrays.sort(x);
        Arrays.sort(y);
        return Arrays.equals(x, y);
    }

    static boolean anaCount(String a, String b) {
        if (a.length() != b.length()) return false;
        int[] cnt = new int[26];
        for (int i = 0; i < a.length(); i++) {
            cnt[a.charAt(i) - 'a']++;
            cnt[b.charAt(i) - 'a']--;
        }
        for (int c : cnt) if (c != 0) return false;
        return true;
    }

    static boolean anaStream(String a, String b) {
        return a.chars().sorted().boxed().toList().equals(b.chars().sorted().boxed().toList());
    }

    // ---------- P09 reverse the words ----------
    static String revWordsBrute(String s) {
        String[] w = s.split(" ");
        String r = "";
        for (int i = w.length - 1; i >= 0; i--) {
            r += w[i];
            if (i > 0) r += " ";
        }
        return r;
    }

    static String revWordsOpt(String s) {
        List<String> l = Arrays.asList(s.trim().split("\\s+"));
        Collections.reverse(l);
        return String.join(" ", l);
    }

    static String revWordsStream(String s) {
        String[] w = s.trim().split("\\s+");
        return IntStream.range(0, w.length).mapToObj(i -> w[w.length - 1 - i]).collect(Collectors.joining(" "));
    }

    // ---------- P10 reverse each word ----------
    static String revEachBrute(String s) {
        String[] w = s.split(" ");
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < w.length; i++) {
            sb.append(reverseBrute(w[i]));
            if (i < w.length - 1) sb.append(' ');
        }
        return sb.toString();
    }

    static String revEachOpt(String s) {
        char[] a = s.toCharArray();
        int start = 0;
        for (int i = 0; i <= a.length; i++) {
            if (i == a.length || a[i] == ' ') {
                for (int l = start, r = i - 1; l < r; l++, r--) {
                    char t = a[l]; a[l] = a[r]; a[r] = t;
                }
                start = i + 1;
            }
        }
        return new String(a);
    }

    static String revEachStream(String s) {
        return Arrays.stream(s.split(" ")).map(w -> new StringBuilder(w).reverse().toString())
                .collect(Collectors.joining(" "));
    }

    // ---------- P11 longest word ----------
    static String longestBrute(String s) {
        String[] w = s.split(" ");
        Arrays.sort(w, (a, b) -> b.length() - a.length());
        return w[0];
    }

    static String longestOpt(String s) {
        String best = "";
        for (String w : s.split(" ")) if (w.length() > best.length()) best = w;
        return best;
    }

    static String longestStream(String s) {
        return Arrays.stream(s.split(" ")).max(Comparator.comparingInt(String::length)).get();
    }

    // ---------- P13 pangram ----------
    static boolean pangramBrute(String s) {
        String l = s.toLowerCase();
        for (char c = 'a'; c <= 'z'; c++) if (l.indexOf(c) < 0) return false;
        return true;
    }

    static boolean pangramOpt(String s) {
        boolean[] seen = new boolean[26];
        int count = 0;
        for (char c : s.toLowerCase().toCharArray()) {
            if (c >= 'a' && c <= 'z' && !seen[c - 'a']) {
                seen[c - 'a'] = true;
                if (++count == 26) return true;
            }
        }
        return false;
    }

    static boolean pangramStream(String s) {
        return s.toLowerCase().chars().filter(c -> c >= 'a' && c <= 'z').distinct().count() == 26;
    }

    // ---------- P14 string rotation ----------
    static boolean rotBrute(String a, String b) {
        if (a.length() != b.length()) return false;
        for (int i = 0; i < a.length(); i++) if ((a.substring(i) + a.substring(0, i)).equals(b)) return true;
        return a.isEmpty();
    }

    static boolean rotOpt(String a, String b) {
        return a.length() == b.length() && (a + a).contains(b);
    }

    // ---------- P15 longest palindromic substring ----------
    static String lpsBrute(String s) {
        String best = "";
        for (int i = 0; i < s.length(); i++)
            for (int j = i + 1; j <= s.length(); j++) {
                String sub = s.substring(i, j);
                if (sub.length() > best.length() && palOpt(sub)) best = sub;
            }
        return best;
    }

    static String lpsOpt(String s) {
        int start = 0, len = 0, n = s.length();
        for (int c = 0; c < n; c++) {
            for (int odd = 0; odd < 2; odd++) {
                int l = c, r = c + odd;
                while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) { l--; r++; }
                int cur = r - l - 1;
                if (cur > len) { len = cur; start = l + 1; }
            }
        }
        return s.substring(start, start + len);
    }

    // ---------- P16 longest substring without repeating characters ----------
    static int lswBrute(String s) {
        int best = 0;
        for (int i = 0; i < s.length(); i++) {
            Set<Character> seen = new HashSet<>();
            for (int j = i; j < s.length(); j++) {
                if (!seen.add(s.charAt(j))) break;
                best = Math.max(best, j - i + 1);
            }
        }
        return best;
    }

    static int lswOpt(String s) {
        Map<Character, Integer> last = new HashMap<>();
        int left = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            Integer prev = last.get(c);
            if (prev != null && prev >= left) left = prev + 1;
            last.put(c, right);
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    // ---------- P17 longest common prefix ----------
    static String common(String a, String b) {
        int i = 0;
        while (i < a.length() && i < b.length() && a.charAt(i) == b.charAt(i)) i++;
        return a.substring(0, i);
    }

    static String lcpBrute(String[] w) {
        String p = w[0];
        for (int i = 1; i < w.length; i++) while (!w[i].startsWith(p)) p = p.substring(0, p.length() - 1);
        return p;
    }

    static String lcpOpt(String[] w) {
        String[] c = w.clone();
        Arrays.sort(c);
        return common(c[0], c[c.length - 1]);
    }

    static String lcpStream(String[] w) {
        return Arrays.stream(w).reduce(StringInterviewPrograms::common).get();
    }

    // ---------- P18 valid parentheses ----------
    static boolean parenBrute(String s) {
        String prev;
        do {
            prev = s;
            s = s.replace("()", "").replace("[]", "").replace("{}", "");
        } while (!s.equals(prev));
        return s.isEmpty();
    }

    static boolean parenOpt(String s) {
        Deque<Character> st = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            switch (c) {
                case '(' -> st.push(')');
                case '[' -> st.push(']');
                case '{' -> st.push('}');
                default -> { if (st.isEmpty() || st.pop() != c) return false; }
            }
        }
        return st.isEmpty();
    }

    // ---------- P19 run-length compression ----------
    static String rleBrute(String s) {
        String r = "";
        int i = 0;
        while (i < s.length()) {
            int j = i;
            while (j < s.length() && s.charAt(j) == s.charAt(i)) j++;
            r = r + s.charAt(i) + (j - i);
            i = j;
        }
        return r;
    }

    static String rleOpt(String s) {
        StringBuilder sb = new StringBuilder();
        int i = 0;
        while (i < s.length()) {
            int j = i;
            while (j < s.length() && s.charAt(j) == s.charAt(i)) j++;
            sb.append(s.charAt(i)).append(j - i);
            i = j;
        }
        return sb.toString();
    }

    static String rleWrongStream(String s) {
        return s.chars().mapToObj(c -> (char) c)
                .collect(Collectors.groupingBy(Function.identity(), LinkedHashMap::new, Collectors.counting()))
                .entrySet().stream().map(e -> "" + e.getKey() + e.getValue()).collect(Collectors.joining());
    }

    // ---------- P20 isomorphic strings ----------
    static String signature(String s) {
        Map<Character, Integer> first = new HashMap<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) sb.append(first.computeIfAbsent(s.charAt(i), k -> first.size())).append(',');
        return sb.toString();
    }

    static boolean isoBrute(String a, String b) {
        return a.length() == b.length() && signature(a).equals(signature(b));
    }

    static boolean isoOpt(String a, String b) {
        if (a.length() != b.length()) return false;
        Map<Character, Character> ab = new HashMap<>(), ba = new HashMap<>();
        for (int i = 0; i < a.length(); i++) {
            char x = a.charAt(i), y = b.charAt(i);
            if (ab.putIfAbsent(x, y) != null && ab.get(x) != y) return false;
            if (ba.putIfAbsent(y, x) != null && ba.get(y) != x) return false;
        }
        return true;
    }

    // ---------- P21 permutations ----------
    static void permute(String prefix, String rest, List<String> out) {
        if (rest.isEmpty()) { out.add(prefix); return; }
        for (int i = 0; i < rest.length(); i++)
            permute(prefix + rest.charAt(i), rest.substring(0, i) + rest.substring(i + 1), out);
    }

    static void swapPerm(char[] a, int k, List<String> out) {
        if (k == a.length) { out.add(new String(a)); return; }
        for (int i = k; i < a.length; i++) {
            char t = a[k]; a[k] = a[i]; a[i] = t;
            swapPerm(a, k + 1, out);
            t = a[k]; a[k] = a[i]; a[i] = t;
        }
    }

    // ---------- P22 distinct substrings ----------
    static Set<String> substrings(String s) {
        Set<String> set = new TreeSet<>();
        for (int i = 0; i < s.length(); i++) for (int j = i + 1; j <= s.length(); j++) set.add(s.substring(i, j));
        return set;
    }

    // ---------- P23 toggle case ----------
    static String toggleBrute(String s) {
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (Character.isUpperCase(c)) sb.append(Character.toLowerCase(c));
            else if (Character.isLowerCase(c)) sb.append(Character.toUpperCase(c));
            else sb.append(c);
        }
        return sb.toString();
    }

    static String toggleOpt(String s) {
        char[] a = s.toCharArray();
        for (int i = 0; i < a.length; i++) {
            char c = a[i];
            if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) a[i] = (char) (c ^ 32);
        }
        return new String(a);
    }

    static String toggleStream(String s) {
        return s.chars().map(c -> Character.isUpperCase(c) ? Character.toLowerCase(c)
                : Character.isLowerCase(c) ? Character.toUpperCase(c) : c)
                .collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append).toString();
    }

    // ---------- P25 count occurrences ----------
    static int countNonOverlap(String s, String sub) {
        int n = 0, i = 0;
        while ((i = s.indexOf(sub, i)) >= 0) { n++; i += sub.length(); }
        return n;
    }

    static int countOverlap(String s, String sub) {
        int n = 0, i = 0;
        while ((i = s.indexOf(sub, i)) >= 0) { n++; i++; }
        return n;
    }

    // ---------- P27 only digits ----------
    static boolean digitsAscii(String s) {
        if (s.isEmpty()) return false;
        for (char c : s.toCharArray()) if (c < '0' || c > '9') return false;
        return true;
    }

    // ---------- P28 title case ----------
    static String titleBrute(String s) {
        StringBuilder sb = new StringBuilder();
        boolean startOfWord = true;
        for (char c : s.toCharArray()) {
            if (c == ' ') { startOfWord = true; sb.append(c); }
            else if (startOfWord) { sb.append(Character.toUpperCase(c)); startOfWord = false; }
            else sb.append(Character.toLowerCase(c));
        }
        return sb.toString();
    }

    static String titleOpt(String s) {
        String[] w = s.split(" ", -1);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < w.length; i++) {
            if (!w[i].isEmpty()) sb.append(Character.toUpperCase(w[i].charAt(0))).append(w[i].substring(1).toLowerCase());
            if (i < w.length - 1) sb.append(' ');
        }
        return sb.toString();
    }

    static String titleStream(String s) {
        return Arrays.stream(s.split(" ", -1))
                .map(w -> w.isEmpty() ? w : Character.toUpperCase(w.charAt(0)) + w.substring(1).toLowerCase())
                .collect(Collectors.joining(" "));
    }

    // ---------- P29 atoi ----------
    static int atoi(String s) {
        int i = 0, n = s.length();
        while (i < n && s.charAt(i) == ' ') i++;
        int sign = 1;
        if (i < n && (s.charAt(i) == '-' || s.charAt(i) == '+')) {
            if (s.charAt(i) == '-') sign = -1;
            i++;
        }
        long v = 0;
        while (i < n && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
            v = v * 10 + (s.charAt(i) - '0');
            if (sign * v > Integer.MAX_VALUE) return Integer.MAX_VALUE;
            if (sign * v < Integer.MIN_VALUE) return Integer.MIN_VALUE;
            i++;
        }
        return (int) (sign * v);
    }

    static String hex(String s) {
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) sb.append(String.format("%04X ", (int) c));
        return sb.toString().trim();
    }

    public static void main(String[] args) {
        // P01
        rep(1, "reverse hello", reverseBrute("hello"), reverseOpt("hello"), reverseStream("hello"));
        // P02
        rep(2, "palindrome racecar", palBrute("racecar"), palOpt("racecar"), palStream("racecar"));
        one(2, "palindrome 'A man, a plan, a canal: Panama' raw / cleaned first",
                palOpt("A man, a plan, a canal: Panama") + " / " + palOpt(clean("A man, a plan, a canal: Panama")));
        // P03
        String vs = "Hello World Java";
        rep(3, "vowels/consonants in '" + vs + "'", vcBrute(vs), vcOpt(vs), vcStream(vs));
        // P04
        rep(4, "char frequency mississippi", freqBrute("mississippi"), freqOpt("mississippi"), freqStream("mississippi"));
        // P05
        rep(5, "first non-repeated char in stress", fnrBrute("stress"), fnrOpt("stress"), fnrStream("stress"));
        // P06
        rep(6, "first repeated char in programming", frBrute("programming"), frOpt("programming"), null);
        // P07
        rep(7, "remove duplicate chars banana", dedupBrute("banana"), dedupOpt("banana"), dedupStream("banana"));
        // P08
        rep(8, "anagram listen/silent", anaSort("listen", "silent"), anaCount("listen", "silent"), anaStream("listen", "silent"));
        rep(8, "anagram hello/world", anaSort("hello", "world"), anaCount("hello", "world"), anaStream("hello", "world"));
        // P09
        rep(9, "reverse words 'java is fun'", revWordsBrute("java is fun"), revWordsOpt("java is fun"), revWordsStream("java is fun"));
        // P10
        rep(10, "reverse each word 'java is fun'", revEachBrute("java is fun"), revEachOpt("java is fun"), revEachStream("java is fun"));
        // P11
        String lw = "the quick brownish fox jumps";
        rep(11, "longest word", longestBrute(lw), longestOpt(lw), longestStream(lw));
        // P12
        String ws = "  hello   world  java ";
        one(12, "word count: split(\" \") / trim().split(\"\\\\s+\") / stream filter",
                ws.split(" ").length + " / " + ws.trim().split("\\s+").length + " / "
                        + Arrays.stream(ws.split("\\s+")).filter(w -> !w.isEmpty()).count());
        one(12, "blank string '   ' word count: trim().split(\"\\\\s+\") / guarded",
                "   ".trim().split("\\s+").length + " / " + ("   ".isBlank() ? 0 : "   ".trim().split("\\s+").length));
        // P13
        String pg = "The quick brown fox jumps over the lazy dog";
        rep(13, "pangram", pangramBrute(pg), pangramOpt(pg), pangramStream(pg));
        rep(13, "pangram 'hello world'", pangramBrute("hello world"), pangramOpt("hello world"), pangramStream("hello world"));
        // P14
        rep(14, "rotation waterbottle/erbottlewat", rotBrute("waterbottle", "erbottlewat"), rotOpt("waterbottle", "erbottlewat"),
                IntStream.range(0, 11).anyMatch(i -> ("waterbottle".substring(i) + "waterbottle".substring(0, i)).equals("erbottlewat")));
        rep(14, "rotation abcd/acbd", rotBrute("abcd", "acbd"), rotOpt("abcd", "acbd"), null);
        // P15
        rep(15, "longest palindromic substring of babad", lpsBrute("babad"), lpsOpt("babad"), null);
        rep(15, "longest palindromic substring of cbbd", lpsBrute("cbbd"), lpsOpt("cbbd"), null);
        // P16
        rep(16, "longest substring without repeats abcabcbb", lswBrute("abcabcbb"), lswOpt("abcabcbb"), null);
        rep(16, "longest substring without repeats pwwkew", lswBrute("pwwkew"), lswOpt("pwwkew"), null);
        // P17
        String[] words = {"flower", "flow", "flight"};
        rep(17, "longest common prefix", lcpBrute(words), lcpOpt(words), lcpStream(words));
        // P18
        List<String> ps = List.of("{[()]}", "([)]", "((");
        rep(18, "valid parentheses " + ps, ps.stream().map(StringInterviewPrograms::parenBrute).toList(),
                ps.stream().map(StringInterviewPrograms::parenOpt).toList(), null);
        // P19
        rep(19, "run-length encode aaabbbccd", rleBrute("aaabbbccd"), rleOpt("aaabbbccd"), null);
        one(19, "stream groupingBy trap on aabaa: correct RLE / groupingBy", rleOpt("aabaa") + " / " + rleWrongStream("aabaa"));
        // P20
        String[][] pairs = {{"egg", "add"}, {"foo", "bar"}, {"paper", "title"}, {"badc", "baba"}};
        List<Boolean> iso1 = new ArrayList<>(), iso2 = new ArrayList<>();
        for (String[] p : pairs) { iso1.add(isoBrute(p[0], p[1])); iso2.add(isoOpt(p[0], p[1])); }
        rep(20, "isomorphic egg/add, foo/bar, paper/title, badc/baba", iso1, iso2, null);
        // P21
        List<String> perm1 = new ArrayList<>(), perm2 = new ArrayList<>();
        permute("", "abc", perm1);
        swapPerm("abc".toCharArray(), 0, perm2);
        Collections.sort(perm1);
        Collections.sort(perm2);
        rep(21, "permutations of abc", perm1, perm2, null);
        List<String> dup = new ArrayList<>();
        permute("", "aab", dup);
        one(21, "permutations of aab: generated / unique", dup.size() + " / " + new TreeSet<>(dup).size() + " " + new TreeSet<>(dup));
        // P22
        String ss = "abab";
        Set<String> subs = substrings(ss);
        long viaStream = IntStream.range(0, ss.length()).boxed()
                .flatMap(i -> IntStream.rangeClosed(i + 1, ss.length()).mapToObj(j -> ss.substring(i, j)))
                .distinct().count();
        one(22, "substrings of abab: all / distinct set / distinct stream",
                ss.length() * (ss.length() + 1) / 2 + " / " + subs.size() + " " + subs + " / " + viaStream);
        // P23
        rep(23, "toggle case 'Hello World 123'", toggleBrute("Hello World 123"), toggleOpt("Hello World 123"), toggleStream("Hello World 123"));
        // P24
        String plain = "a1 b2, c3!";
        String accent = "café 1!";
        one(24, "strip non-alphanumerics from 'a1 b2, c3!': regex / isLetterOrDigit",
                plain.replaceAll("[^A-Za-z0-9]", "") + " / "
                        + plain.chars().filter(Character::isLetterOrDigit).collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append));
        String r1 = accent.replaceAll("[^A-Za-z0-9]", "");
        String r2 = accent.chars().filter(Character::isLetterOrDigit).collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append).toString();
        one(24, "same on 'caf' + e-acute + ' 1!': regex length / isLetterOrDigit length / e-acute kept by each",
                r1.length() + " / " + r2.length() + " / " + (r1.indexOf('é') >= 0) + " , " + (r2.indexOf('é') >= 0));
        // P25
        one(25, "count 'aa' in 'aaaa': non-overlapping / replace trick / overlapping / overlapping stream",
                countNonOverlap("aaaa", "aa") + " / " + ("aaaa".length() - "aaaa".replace("aa", "").length()) / "aa".length() + " / "
                        + countOverlap("aaaa", "aa") + " / "
                        + IntStream.range(0, "aaaa".length() - "aa".length() + 1).filter(i -> "aaaa".startsWith("aa", i)).count());
        // P26
        String a = "hello", b = "world";
        a = a + b;
        b = a.substring(0, a.length() - b.length());
        a = a.substring(b.length());
        one(26, "swap 'hello' and 'world' without a temp variable", "a=" + a + ", b=" + b);
        // P27
        String[] ins = {"12345", "12a45", "", "١٢٣"};
        String[] names = {"12345", "12a45", "empty", "arabic-indic"};
        for (int i = 0; i < ins.length; i++) {
            String s = ins[i];
            one(27, "digits only? " + names[i] + " : regex \\d+ / allMatch(isDigit) / ascii loop",
                    s.matches("\\d+") + " / " + s.chars().allMatch(Character::isDigit) + " / " + digitsAscii(s));
        }
        // P28
        String tc = "hello wORLD from java";
        rep(28, "title case", titleBrute(tc), titleOpt(tc), titleStream(tc));
        // P29
        for (String s : new String[] {"  -42abc", "4193 with words", "words 987", "2147483648", "-91283472332"})
            one(29, "atoi('" + s + "')", atoi(s));
        try {
            Integer.parseInt("  -42abc");
        } catch (NumberFormatException e) {
            one(29, "Integer.parseInt('  -42abc')", e.getClass().getSimpleName() + ": " + e.getMessage());
        }
        // P30
        String emoji = "a😀b";
        String loop = reverseBrute(emoji);
        String sbRev = reverseOpt(emoji);
        int[] cps = emoji.codePoints().toArray();
        StringBuilder cpb = new StringBuilder();
        for (int i = cps.length - 1; i >= 0; i--) cpb.appendCodePoint(cps[i]);
        String cpRev = cpb.toString();
        one(30, "'a'+grinning-face+'b': length() / codePointCount", emoji.length() + " / " + emoji.codePointCount(0, emoji.length()));
        one(30, "char-by-char reverse UTF-16 units", hex(loop) + " (equals correct reverse: " + loop.equals("b😀a") + ")");
        one(30, "StringBuilder.reverse UTF-16 units", hex(sbRev) + " (equals correct reverse: " + sbRev.equals("b😀a") + ")");
        one(30, "codePoints-based reverse equals correct", cpRev.equals("b😀a"));

        // ---------- timings (noisy; JIT warm-up included for both) ----------
        String big = "x".repeat(50_000);
        reverseOpt(big);
        long t0 = System.nanoTime();
        reverseBrute(big);
        long concat = (System.nanoTime() - t0) / 1_000_000;
        t0 = System.nanoTime();
        reverseOpt(big);
        long sb = (System.nanoTime() - t0) / 1_000_000;
        System.out.println("BENCH reverse 50000 chars: concatenation loop " + concat + " ms, StringBuilder " + sb + " ms");

        String pal = "ab".repeat(300);
        lpsOpt(pal);
        t0 = System.nanoTime();
        String x1 = lpsBrute(pal);
        long bruteMs = (System.nanoTime() - t0) / 1_000_000;
        t0 = System.nanoTime();
        String x2 = lpsOpt(pal);
        long optMs = (System.nanoTime() - t0) / 1_000_000;
        System.out.println("BENCH longest palindromic substring of a 600-char string: brute " + bruteMs + " ms, expand-around-center "
                + optMs + " ms, same answer " + x1.equals(x2));
    }
}