Cost of a loop, next perm, parse then count

Honest Big-O

This is a table, not a Live Code problem. Two tiny pictures: HashMap get is not always O(1), and recursion is not O(1) extra just because you wrote no array.

Example 1 — simple

HashMap average vs a collision chain. Same three puts; different bucket layouts.

Map<Integer, Integer> m = new HashMap<>();
m.put(2, 0);
m.put(7, 1);
m.get(7);   // typical: hash 7 lands in its bin, one entry — O(1)
            // worst picture: 2 and 7 (and n other keys) all hash to one bin;
            // get walks that chain — O(n) until the table treeifies comparable keys

Answer: say “O(1) average, O(n) if everything collides” — not “HashMap is always O(1).”

Example 2 — every step

Recursion stack space. Sum 1..4 with a call per n. Time is O(n); extra memory is also O(n) frames, even though you allocated no array.

int sum(int n) {
    if (n == 0) return 0;     // one frame still sits here until the child returns
    return n + sum(n - 1);    // n frames live at the bottom: sum(4)→sum(3)→sum(2)→sum(1)→sum(0)
}

Answer: result 10. Peak stack 5 frames. Tail-recursion does not save you in Java — there is no tail-call elimination on this pattern.

StringBuilder vs + in a loop

Recognize it from — build a string of length n from pieces, add two huge digit-strings, serialize a count key, reverse a character buffer. Java String is immutable; each + allocates a new one.

What it actually does — s = s + ch copies every character already in s into a new object, then appends ch. After n appends of one char, you copied 1+2+…+n characters — quadratic. StringBuilder keeps one growing buffer (amortized doubling) and copies each character a constant number of times.

String repeatPlus(int n) {
    String s = "";
    for (int i = 0; i < n; i++) {
        s = s + "a";   // new String object every time; copies s.length() chars
    }
    return s;
}

String repeatSb(int n) {
    StringBuilder sb = new StringBuilder(n); // capacity hint — one buffer
    for (int i = 0; i < n; i++) sb.append('a'); // amortized O(1) per char
    return sb.toString();
}
String addLong(String a, String b) {         // schoolbook add: same builder habit
    StringBuilder sb = new StringBuilder();
    int i = a.length() - 1, j = b.length() - 1, c = 0;
    while (i >= 0 || j >= 0 || c > 0) {
        int s = c;
        if (i >= 0) s += a.charAt(i--) - '0';
        if (j >= 0) s += b.charAt(j--) - '0';
        sb.append(s % 10);
        c = s / 10;
    }
    return sb.reverse().toString();
}

Example 1 — simple

n = 3 concatenations. Count the objects and the character copies.

Answer: 3 new String objects (plus the empty start). Character copies 1+2+3 = 6, not 3.

Example 2 — every step

n = 5. Quadratic copies vs StringBuilder.

Answer: + copied 15 characters (1+2+3+4+5). Builder copied 5 into its buffer (plus a possible grow, none if capacity was n). For general n, + is Θ(n²).

Next permutation — pivot, swap, reverse suffix

Recognize it from — next lexicographic permutation of an array; wrap to sorted-ascending if this is already the last. “Next greater number with the same digits” is the same walk on a digit array. Next greater element is a stack — different chapter.

What it actually does — from the right, find the first ascent a[i] < a[i+1] (the pivot: the rightmost place we can increase). If none, the array is non-increasing — reverse all of it. Otherwise find the rightmost a[j] > a[i] (the suffix is non-increasing, so that j is the smallest successor), swap i and j, then reverse the suffix after i so it becomes the smallest tail.

void nextPermutation(int[] a) {
    int n = a.length;
    int i = n - 2;
    while (i >= 0 && a[i] >= a[i + 1]) i--; // walk right → left until an ascent (pivot)
    if (i >= 0) {
        int j = n - 1;
        while (a[j] <= a[i]) j--;           // rightmost successor strictly greater than pivot
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
    reverse(a, i + 1, n - 1);               // suffix was decreasing; reverse → smallest tail
}
void reverse(int[] a, int l, int r) {
    while (l < r) {
        int t = a[l]; a[l] = a[r]; a[r] = t;
        l++; r--;
    }
}

void nextPermutation(int[] a) {
    if (a == null || a.length <= 1) return;
    int n = a.length, i = n - 2;
    while (i >= 0 && a[i] >= a[i + 1]) i--;
    if (i >= 0) {
        int j = n - 1;
        while (a[j] <= a[i]) j--;
        int t = a[i]; a[i] = a[j]; a[j] = t; // in-place swap
    }
    for (int l = i + 1, r = n - 1; l < r; l++, r--) { // in-place reverse, no helper if they want one method
        int t = a[l]; a[l] = a[r]; a[r] = t;
    }
}

Example 1 — simple

[1, 2, 3] → [1, 3, 2].

Answer: [1, 3, 2].

Example 2 — every step

[1, 3, 2] → [2, 1, 3]. Every index from the right.

Answer: [2, 1, 3]. Do not stamp an LC id on the AUTA “similar to next permutation” write-up.

Encoded string frequency — index walk

Recognize it from — a string of digits, #, and (k) that encodes letters; output letter counts. The notebook sample is 1226#24#(2). The grammar in that IE was not fully specified — say the assumption out loud, then parse. This is not “sum two long digit strings.”

Assumed grammar (same as chapter 05, from the sample): a single digit d is letter a..i (1→a … 9→i). Two digits followed by # is letter j..z (10#→j … 26#→z). Greedy: try the two-digit # token first. An optional (k) immediately after a token multiplies that token’s count. Unknown letters / other symbols: ask; this booklet does not invent extra productions.

What it actually does — walk an index i. At each step parse one token, then an optional multiplier, then add into a count array. Do not expand (k) into k copies of the letter when they only asked for frequencies — that blows up huge k.

Map<Character, Integer> freqEncoded(String s) {
    Map<Character, Integer> map = new HashMap<>();
    int i = 0, n = s.length();
    while (i < n) {
        int code, j;
        if (i + 2 < n && Character.isDigit(s.charAt(i))
                && Character.isDigit(s.charAt(i + 1)) && s.charAt(i + 2) == '#') {
            code = Integer.parseInt(s.substring(i, i + 2)); // 10#..26# before a lone digit
            j = i + 3;                                       // skip the two digits and '#'
        } else {
            code = s.charAt(i) - '0';                        // 1..9 → a..i
            j = i + 1;
        }
        int times = 1;
        if (j < n && s.charAt(j) == '(') {                   // optional (k) multiplies this token
            int k = j + 1;
            while (k < n && s.charAt(k) != ')') k++;
            times = Integer.parseInt(s.substring(j + 1, k));
            j = k + 1;
        }
        map.merge((char) ('a' + code - 1), times, Integer::sum);
        i = j;                                               // next token
    }
    return map;
}

int[] freqEncodedCounts(String s) {
    int[] cnt = new int[26];           // no HashMap, no expanded string
    int i = 0, n = s.length();
    while (i < n) {
        int code, j;
        if (i + 2 < n && Character.isDigit(s.charAt(i))
                && Character.isDigit(s.charAt(i + 1)) && s.charAt(i + 2) == '#') {
            code = (s.charAt(i) - '0') * 10 + (s.charAt(i + 1) - '0');
            j = i + 3;
        } else {
            code = s.charAt(i) - '0';
            j = i + 1;
        }
        int times = 1;
        if (j < n && s.charAt(j) == '(') {
            int k = j + 1, val = 0;
            while (k < n && s.charAt(k) != ')') val = val * 10 + (s.charAt(k++) - '0');
            times = val;               // add times into cnt — do not loop times appending a letter
            j = k + 1;
        }
        cnt[code - 1] += times;
        i = j;
    }
    return cnt;
}

Example 1 — simple

Locked tiny string: 12#. Under the grammar above, that is one token: two digits plus # → letter 12 → l. It is not 1 then 2 then leftover #, because the two-digit rule is greedy.

Answer: l once. Four-token drill defined next, still under this grammar.

Example 2 — every step

Four-token string we define: 10#11#2(3)3 → tokens 10#, 11#, 2(3), 3. Letters j, k, b×3, c. The notebook family sample 1226#24#(2) uses the same grammar — dry-run lives on the ch.05 card; do not invent extra productions.

Answer: j=1, k=1, b=3, c=1. Family sample on ch.05 encoded-frequency: 1→a, 2→b, 26#→z, 24#(2)→x×2. Confirm grammar before coding if they hand you a different string.