String Permutations

Forty-five answers, ten million calls

List every distinct rearrangement of aaaaaaaabb: eight a's and two b's. The standard permutation template treats the ten letters as ten different objects. It makes 9,864,101 recursive calls and outputs 3,628,800 strings. Only 45 of them are different. Each one comes out 80,640 times. A set at the end cleans up the output, but it does not give you back the ten million calls. The generator you will build in this lesson makes 219.

Now a different request. Does a 10,000-letter string s2 contain some rearrangement of a 10-letter string s1? Generating up to 3,628,800 rearrangements of s1 (exactly that many when its letters are distinct) and searching for each one is hopeless. And you never needed them. A slice of s2 is a rearrangement of s1 exactly when the two have the same letter counts, and there are only 9,991 slices of length 10 to check.

Both fixes rest on one idea: a string's arrangements are determined by its letter counts. Work with the counts: draw letters from them, count arrangements with them, compare them. Only list an arrangement when you actually have to output it.

This lesson builds on Permutations & Combinations: the choose/explore/unchoose template, the used array, the Counter version of Permutations II, and why n distinct items have n! orders. Advanced Recursion & Backtracking has the call-stack picture. From Foundation: Arrays & Strings you need count vectors, the in-place reverse helper, and the habit of building a string in a list and joining it once.

Warm-up: count before you generate

With n distinct letters there are n! arrangements. abc has 3! = 6.

Repeated letters change the count. Put temporary labels on the copies, as in a₁ a₂ b. The labelled letters are distinct, so there are 3! = 6 labelled arrangements. Now erase the labels. a₁ a₂ b and a₂ a₁ b both become aab. In general, every plain string comes from exactly c₁! × c₂! × … × c_k! labelled ones, where c₁, …, c_k are the letter counts: that is the number of ways to shuffle the labels among the positions of identical letters. So divide:

distinct arrangements = n! / (c₁! × c₂! × … × c_k!)

This is the multinomial coefficient. Call it M; the rest of the lesson uses that name.

Every count divides, not just the first repeated one. Dividing aabb's 24 by 2! alone gives 12, which double-counts. The b's need their own 2!.

Predict first: how many distinct strings can you make by rearranging banana?

Why count first

Listing M strings of length n writes n × M characters. No generator can do less, so any "return them all" solution needs at least n·M steps. The count tells you whether listing is even possible. Python needs a few seconds to list the 10! = 3,628,800 arrangements of ten distinct letters. With twelve letters, 12! = 479,001,600, and listing them is out of reach. That is why problems that ask for all of them keep inputs tiny: LeetCode 46: Permutations allows at most 6 numbers, and LeetCode 47: Permutations II at most 8.

And 0! = 1: the empty string has exactly one arrangement, the empty one. Keep that in mind when you decide what your generator returns for "".

Your turn: the 30 distinct arrangements of aabbc are listed in dictionary order. How many start with a, and how many with c? Try to get there without writing all 30.

Move 1: Draw from a letter bag

Smell: the problem says "return all unique permutations", the input can repeat letters, and your output contains the same string several times. Or you notice you're about to reach for a set to clean up at the end.

The echo in the tree

Predict first: run the plain position-based template (no duplicate handling) on aaaaaaaabb. How many strings does it output, and how many of those are aaaaaaaabb itself?

Here is the slow version: the position template, with a set at the end.

def distinct_perms_slow(s):
    n = len(s)
    used = [False] * n
    path, out = [], set()

    def build():
        if len(path) == n:
            out.add("".join(path))
            return
        for i in range(n):              # choose a POSITION of s
            if used[i]:
                continue
            used[i] = True
            path.append(s[i])
            build()
            path.pop()
            used[i] = False

    build()
    return sorted(out)

Watch what it repeats on aab. At the root it tries position 0 (an a) and position 1 (also an a), and the two subtrees below them are identical:

positions a₁ a₂ b: 6 leaves              letters {a:2, b:1}: 3 leaves
a₁ ─ a₂ ─ b     aab                      a ─ a ─ b     aab
   └ b ── a₂    aba                        └ b ─ a     aba
a₂ ─ a₁ ─ b     aab   (echo)             b ─ a ─ a     baa
   └ b ── a₁    aba   (echo)
b ── a₁ ─ a₂    baa
   └ a₂ ─ a₁    baa   (echo)

The recursion tells copies apart even though the output can't. The fix is to choose letters, not positions: at each step, try each distinct letter once.

Choose letters, not positions

Keep a bag: a count of how many copies of each letter are still unused. This is the count vector from Foundation, stored in a Counter. If you met the Counter version of Permutations II in Permutations & Combinations, this is the same generator. For strings it is the natural default, and the rest of this lesson builds on it. Drawing a letter decrements its count, and putting it back increments it.

from collections import Counter

def distinct_perms(s):
    bag = Counter(s)                 # letter -> copies not yet placed
    letters = sorted(bag)            # each distinct letter once, in order
    n = len(s)
    path, out = [], []

    def build():
        if len(path) == n:
            out.append("".join(path))
            return
        for ch in letters:
            if bag[ch] == 0:
                continue
            bag[ch] -= 1             # choose: draw one copy of ch
            path.append(ch)
            build()                  # explore
            path.pop()               # unchoose: put it back
            bag[ch] += 1

    build()
    return out

print(distinct_perms("aab"))         # ['aab', 'aba', 'baa']

Every call to build on aab, in order:

Nine calls, three outputs, no echoes. The position template makes 16 calls on the same input.

Why it works

The invariant: before every call, bag holds exactly the letters of s that are not in path. Each draw moves one letter from the bag to the path, and each undo moves it back.

• No duplicates. Two sibling calls put different letters at the same position. So every string under one sibling differs from every string under the other at that position. Any two leaves split at some call, so any two outputs differ.
• Nothing missing. Take any distinct arrangement. At each position its next letter is still in the bag, because the bag is exactly what hasn't been placed yet. So the generator can follow that arrangement all the way down.
• Sorted for free. Letters are tried in sorted order at every level, so the output comes out in dictionary order.

What it costs

Let k be the number of distinct letters. While the path is incomplete, the bag is not empty, so every call either outputs a string or has at least one child. Calls at the same depth hold different prefixes, and each prefix leads to at least one output of its own. So each depth has at most M calls, and there are at most n·M + 1 calls in total.

Each call scans k letters, and each output costs O(n) to join. That gives O(k·n·M) time. For a fixed alphabet such as 26 lowercase letters, k ≤ 26 and this is O(n·M), the same as the size of the output, so asymptotically you can't do better. Extra space besides the output is O(n + k): the path and the recursion stack are n deep, and the bag has k entries.

On aaaaaaaabb the difference is dramatic:

Traps

⚠️ Append a snapshot, not the list. out.append(path) stores a reference to the one path list. Backtracking empties that list, so on abc you get [[], [], [], [], [], []]. "".join(path) builds a new string. For list outputs, use path[:].

⚠️ Every draw needs its undo. Delete bag[ch] += 1 and abc returns only ['abc']. The letters drawn for the first string never go back, so every later branch finds an empty bag.

Base case. For full arrangements, len(path) == n and "the bag is empty" are the same test. They differ once you stop early (length-k arrangements, below). There, only the length test is right.

Strings or lists? Passing prefix + ch down the recursion instead of path copies the prefix at every call. In practice this matters less than you might fear, because most calls sit near the leaves. With n distinct letters there are n!/(n − d)! calls at depth d, about e·n! ≈ 2.72·n! in all. For eight letters, 80,640 of the 109,601 calls are on the last two levels, and a leaf pays O(n) to join anyway. In CPython the two versions ran within a few percent of each other, and the concatenating one was slightly faster on nine and ten distinct letters. Use the list-and-join habit because its cost is predictable, not because concatenation is a disaster here.

If you index positions: the twin rule

Permutations & Combinations dedupes the position template differently. It sorts the letters, then skips a letter when an identical letter to its left is still unused:

def twin_rule_perms(s):
    chars = sorted(s)                # twins become neighbours
    n = len(chars)
    used = [False] * n
    path, out = [], []

    def build():
        if len(path) == n:
            out.append("".join(path))
            return
        for i in range(n):
            if used[i]:
                continue
            if i > 0 and chars[i] == chars[i - 1] and not used[i - 1]:
                continue             # my left twin hasn't gone yet
            used[i] = True
            path.append(chars[i])
            build()
            path.pop()
            used[i] = False

    build()
    return out

Read the skip as a queue rule: identical letters leave the bag left to right. Only one labelling of each string survives, the one where a₁ comes before a₂ comes before a₃. So each distinct string appears once. The sort is essential, because the rule only compares neighbours.

Plot twist: flip the condition to and used[i - 1]. The output is still correct: every distinct string appears exactly once, and both versions match a brute-force reference on 1,500 random strings. The flipped rule forces twins to leave right to left instead, which is also exactly one labelling per string. What changes is when the dead branches die:

With not used[i - 1], a wrong twin is refused at the first level where it is offered, so the echo subtree is never entered. With used[i - 1], the generator happily places a₁ first, walks deep into that subtree, and only discovers near the leaves that a₂ can never be placed. Both are correct; one prunes at the top and the other at the bottom. The letter bag makes the same calls as the good twin rule but scans only k letters per call instead of all n positions, so the twin rule costs O(n²·M) where the bag costs O(k·n·M).

If you swap: one set per level

The swap generator fixes position start by swapping each candidate into it, recursing on start + 1, and swapping back. The twin rule does not carry over, because swaps scramble the suffix and identical letters stop being neighbours. Sort aabc, add "skip if i > start and chars[i] == chars[i - 1]", and you get 14 strings, with caab and caba twice each. The fix is to remember which letters you have already placed at this position:

def swap_perms(s):
    chars = list(s)
    out = []

    def build(start):
        if start == len(chars):
            out.append("".join(chars))
            return
        tried = set()                    # letters already placed at `start`
        for i in range(start, len(chars)):
            if chars[i] in tried:
                continue
            tried.add(chars[i])
            chars[start], chars[i] = chars[i], chars[start]
            build(start + 1)
            chars[start], chars[i] = chars[i], chars[start]   # swap back

    build(0)
    return out

print(swap_perms("abc"))   # ['abc', 'acb', 'bac', 'bca', 'cba', 'cab']

Three things to know about the swap version:

• Its order is not dictionary order. Look at the end: cba comes before cab. The third top-level swap exchanges positions 0 and 2, which leaves b in front of a. If the problem wants sorted output, use the bag or sort at the end.
• Either base case works. start == len(chars) - 1 is also correct for every non-empty string: when one position is left, the only swap is a letter with itself. The two versions differ only on "", which gives [""] with the first and [] with the second.
• Forget the swap-back and the output goes quietly wrong. In the plain swap generator (no tried set), abc still returns six strings, ['abc', 'acb', 'cab', 'cba', 'abc', 'acb']: two repeated and two (bac, bca) missing. A test that only checks len(result) == 6 passes. With the tried set, the repeats are skipped and you get only the first four.

Bend the template: shorter strings and rules

Two common variations each change one line of distinct_perms.

Length-k arrangements. Change the base case to len(path) == k. With aab and k = 2 you get ['aa', 'ab', 'ba']. For distinct letters there are n! / (n − k)! of them. The output then has k × count characters, and that is the new floor.

Rules about neighbours. Say no two equal letters may touch. Check the rule before drawing, so a bad branch is never entered:

        for ch in letters:
            if bag[ch] == 0 or (path and path[-1] == ch):
                continue

aab gives ['aba'], aabb gives ['abab', 'baba'], and aaab gives []. If you only checked the rule at the leaves, you would walk the whole tree and throw most of it away.

⚠️ A rule does not remove duplicates. Put the same neighbour check into the position template with no twin rule, and AAB returns ['ABA', 'ABA']: A₁BA₂ and A₂BA₁ both pass the check. Pruning and deduplication are separate jobs.

When your generator lies

Symptoms narrow the search. A brute-force reference proves the fix. itertools.permutations is slow but obviously right on short strings:

import itertools, random

def reference(s):
    return sorted({"".join(p) for p in itertools.permutations(s)})

def check(generate, trials=500):
    for _ in range(trials):
        s = "".join(random.choice("aabc") for _ in range(random.randint(0, 6)))
        got = generate(s)
        assert sorted(got) == reference(s), (s, got)   # also rules out repeats
    print("all matched")

check(distinct_perms)

The alphabet "aabc" makes repeated letters likely. Lengths from 0 to 6 cover the empty string and single letters, and 500 trials almost surely include all-equal strings too.

Your turn: count the tile words

You have letter tiles AAB. How many different non-empty words can you spell, using each tile at most once? The answer is 8: A, B, AA, AB, BA, AAB, ABA, BAA. This is LeetCode 1079: Letter Tile Possibilities. Adapt the bag generator to count them without building any strings. What is the answer for AAABBC?

from collections import Counter

def num_tile_possibilities(tiles):
    bag = Counter(tiles)

    def count():
        total = 0
        for ch in bag:
            if bag[ch] > 0:
                bag[ch] -= 1
                total += 1 + count()    # this word, plus its extensions
                bag[ch] += 1
        return total

    return count()

print(num_tile_possibilities("AAB"), num_tile_possibilities("AAABBC"))   # 8 188

Move 2: Roll to the next arrangement

Smell: "the next lexicographically greater arrangement", "rearrange in place using only constant extra memory", "the smallest number bigger than n with the same digits", or "visit every arrangement without recursion".

Predict first: among the arrangements of the letters of dcfeba, which one comes right after dcfeba in dictionary order?

The slow version generates every arrangement in order, finds the current one, and returns the next. That is O(n·M) time and memory to answer a question about one neighbour. For 20 distinct letters, M = 20! ≈ 2.4 × 10¹⁸.

It wastes everything because the neighbour is close. The next string keeps the longest possible prefix and changes only a suffix. A car odometer rolls over the same way: it bumps the rightmost digit that can still go up and resets everything to its right to the smallest value. (Foundation used odometer readings for prefix sums; here only the roll-over matters.) Here the analogy stops. Odometer digits are independent, but your letters are a fixed collection. "Going up" must borrow a bigger letter from the suffix, and the "reset" must reuse exactly the letters that are left.

Pivot, successor, reverse

def reverse(a, lo, hi):                 # Foundation's helper: reverse a[lo..hi]
    while lo < hi:
        a[lo], a[hi] = a[hi], a[lo]
        lo += 1
        hi -= 1

def next_permutation(a):
    """Step list a to the next larger arrangement, in place.
    From the largest arrangement it wraps to the smallest and returns False."""
    i = len(a) - 2
    while i >= 0 and a[i] >= a[i + 1]:  # 1. pivot: rightmost a[i] < a[i+1]
        i -= 1
    if i >= 0:
        j = len(a) - 1
        while a[j] <= a[i]:             # 2. successor: rightmost a[j] > a[i]
            j -= 1
        a[i], a[j] = a[j], a[i]         # 3. swap them
    reverse(a, i + 1, len(a) - 1)       # 4. smallest order for the suffix
    return i >= 0

a = list("dcfeba")
next_permutation(a)
print("".join(a))                       # deabcf

Python strings are immutable, so the function works on a list of characters (Foundation, Move 5). On dcfeba:

Now start from the smallest arrangement and keep stepping. On aabb, a string with repeated letters:

It visits six strings, which is 4! / (2! × 2!), each exactly once and in order. Duplicates need no special handling. The >= in step 1 and the <= in step 2 already treat equal letters as "not bigger".

def all_in_order(s):
    a = sorted(s)                        # start from the smallest arrangement
    out = ["".join(a)]
    while next_permutation(a):
        out.append("".join(a))
    return out

print(all_in_order("aabb"))   # ['aabb', 'abab', 'abba', 'baab', 'baba', 'bbaa']

Why it works

1. The suffix after the pivot never rises. That makes it the largest arrangement of its letters, so nothing that only touches the suffix can make the string bigger. Position i must change, and keeping everything before i fixed keeps the result as close as possible.
2. Position i grows by the least possible amount. The suffix never rises, so the rightmost letter bigger than a[i] is the smallest such letter.
3. The swap keeps the suffix non-increasing. Letters left of j are at least a[j], which is bigger than a[i]. Letters right of j are at most a[i]. So a[i] fits into slot j without breaking the order. Reversing a non-increasing run makes it non-decreasing: the smallest arrangement of those letters.

Together, the result is the smallest string bigger than the input. Nothing lies between.

Cost. Each step is O(n) time in the worst case and uses O(1) extra space: a few indices and swaps, all in place. The character list itself takes O(n), but you need that to hold the string at all. That is what "in place, constant extra memory" in LeetCode 31: Next Permutation asks for. Enumerating everything costs O(n·M), including copying each output. There's no recursion stack and no bag.

Traps

⚠️ Strict > in step 1 treats an equal pair as a rise. On abb the pivot lands on the first b (index 1), which only equals its neighbour. Step 2 then finds no bigger letter, walks off the front of the list, and raises IndexError. Python's negative indices hide this for a few steps before it crashes. On inputs without repeats > and >= behave identically, so tests with distinct letters never catch it.

⚠️ Strict < in step 2 can swap the pivot with an equal letter: aba becomes aab, which is smaller.

Skipping the reverse gives a bigger string, but not the next one. dcfeba becomes defcba and skips everything in between.

Enumerate from the sorted string. Starting from s itself lists only the arrangements from s onward.

Know what the largest arrangement should do. LeetCode 31 wants it to wrap around to the smallest. The code above does that (with i = −1 it reverses the whole list) and returns False so a loop can stop.

Your turn: write prev_permutation(a), which steps to the next smaller arrangement. Predict what it does to baab and to aabb.

def prev_permutation(a):
    i = len(a) - 2
    while i >= 0 and a[i] <= a[i + 1]:
        i -= 1
    if i >= 0:
        j = len(a) - 1
        while a[j] >= a[i]:
            j -= 1
        a[i], a[j] = a[j], a[i]
    reverse(a, i + 1, len(a) - 1)
    return i >= 0

Move 3: Jump to the k-th arrangement

Smell: "return the k-th permutation in order", with k anywhere up to n!.

Predict first: list the 24 arrangements of 1234 in order. Which digit starts the 9th? Which starts the 17th?

The slow version starts at 123…n and calls next_permutation k − 1 times. Be honest about when that is enough. LeetCode 60: Permutation Sequence caps n at 9, so k − 1 is at most 362,879 steps, and stepping passes. It breaks when k is astronomical: with n = 20, k can reach 20! ≈ 2.4 × 10¹⁸.

What stepping repeats is walking through entire blocks one arrangement at a time, when the size of a block is one factorial.

from math import factorial

def get_permutation(n, k):
    digits = [str(d) for d in range(1, n + 1)]
    k -= 1                                   # 0-based rank
    out = []
    for remaining in range(n, 0, -1):
        block = factorial(remaining - 1)     # arrangements per choice of next digit
        idx, k = divmod(k, block)            # which block, and rank inside it
        out.append(digits.pop(idx))
    return "".join(out)

print(get_permutation(4, 9))                 # 2314

get_permutation(4, 9), with 0-based rank 8:

Why it works

The invariant: before each position, k is the 0-based rank of the answer among the arrangements of the digits still unused. Those arrangements come in blocks of (remaining − 1)!, one block per possible next digit, and the blocks are in the same order as digits. divmod splits the rank into "which block" and "rank inside the block". The second part is exactly the invariant for the next position.

Cost. There are n positions, and digits.pop(idx) shifts up to n entries, so the time is O(n²). For n ≤ 9 that is nothing. (With a Fenwick tree over the unused digits, see Trees & Advanced Structures, a binary search over prefix counts finds the idx-th unused digit in O(log² n), and a Fenwick descent does it in O(log n).) Space is O(n).

Integer size. Python integers don't overflow. In Java or C++, 20! ≈ 2.43 × 10¹⁸ still fits in a signed 64-bit integer (max ≈ 9.22 × 10¹⁸), but 21! does not.

⚠️ Forgetting k -= 1 treats the 1-based k as a 0-based rank, which gives the next arrangement. get_permutation(4, 9) returns 2341 instead of 2314, and asking for the last one, k = n!, raises IndexError.

Your turn — repeated letters: find the 20th distinct arrangement of aabbc in dictionary order. The blocks are no longer equal, but the warm-up told you their sizes.

from collections import Counter
from math import factorial

def count_arrangements(bag):
    total = factorial(sum(bag.values()))
    for c in bag.values():
        total //= factorial(c)
    return total

def kth_distinct(s, k):
    bag = Counter(s)
    k -= 1                                    # 0-based rank
    out = []
    for remaining in range(len(s), 0, -1):
        for ch in sorted(bag):
            if bag[ch] == 0:
                continue
            block = count_arrangements(bag) * bag[ch] // remaining
            if k < block:                     # the answer starts with ch
                out.append(ch)
                bag[ch] -= 1
                break
            k -= block                        # skip ch's whole block
    return "".join(out)

print(kth_distinct("aabbc", 20))              # bbaca

Move 4: Don't generate — slide a count window

Smell: "does s2 contain a permutation of s1?", "find all anagrams of p in s", "is some rearrangement of X a substring of Y?". The question is about any arrangement, so you never need to list them.

Predict first: is some rearrangement of ab a substring of eidbaooo? At most how many substrings must you examine?

This is LeetCode 567: Permutation in String. There are two slow versions. The first generates the arrangements of s1 (up to m!, where m = len(s1)) and searches for each one, which for m = 10 means up to 3,628,800 searches. The second checks each of the n − m + 1 windows by counting its letters from scratch, at O(m) per window. The second one repeats a lot: neighbouring windows share m − 1 letters. Only one letter enters and one leaves.

Keep a count of the window and update it by those two letters:

def check_inclusion(s1, s2):
    m = len(s1)
    if m > len(s2):
        return False
    need = [0] * 26                      # letter counts of s1
    window = [0] * 26                    # letter counts of the current window
    for ch in s1:
        need[ord(ch) - ord('a')] += 1
    for right, ch in enumerate(s2):
        window[ord(ch) - ord('a')] += 1                  # ch enters
        if right >= m:
            window[ord(s2[right - m]) - ord('a')] -= 1   # the letter m back leaves
        if window == need:
            return True
    return False

print(check_inclusion("ab", "eidbaooo"), check_inclusion("ab", "eidboaoo"))   # True False

Why it works

Foundation's anagram fact does the heavy lifting: two strings are rearrangements of each other exactly when their count vectors are equal. The loop keeps an invariant: after processing index right, window counts the last m letters of s2 up to right (or all of them, while fewer than m have been read). The letter that leaves when s2[right] enters is s2[right - m], exactly m steps back.

The first m − 1 steps don't need a guard. A window with fewer than m letters has a smaller total than need, so it can't be equal.

Cost. Each step does O(1) updates plus a comparison of two 26-slot lists. That is O(26 · n) = O(n) time for a fixed alphabet and O(1) extra space: two arrays of 26 no matter how long the strings are.

Traps

⚠️ The leaving index. Removing s2[right - m + 1] removes a letter that is still inside the window. The code then returns False on ("ab", "eidbaooo").

Alphabet. This assumes lowercase a–z, as LeetCode 567 promises. Other characters hit Foundation's negative-index trap. For wider alphabets, use 128 slots for ASCII or a dictionary for Unicode.

Counter equality depends on the Python version. Since Python 3.10, Counter(a=1, b=0) == Counter(a=1) is True, because missing letters count as zero. Before 3.10 it was False. That is why older solutions del a letter's key when its count drops to zero.

from collections import Counter

def check_inclusion_any_alphabet(s1, s2):
    m = len(s1)
    if m > len(s2):
        return False
    diff = Counter(s1)            # count in s1 minus count in the window
    bad = len(diff)               # letters whose diff is not zero

    def shift(ch, delta):
        nonlocal bad
        if diff[ch] == 0:
            bad += 1              # a balanced letter is about to go off balance
        diff[ch] += delta
        if diff[ch] == 0:
            bad -= 1              # this letter just came back into balance

    for right, ch in enumerate(s2):
        shift(ch, -1)                     # ch enters the window
        if right >= m:
            shift(s2[right - m], +1)      # the letter m back leaves
        if bad == 0:
            return True
    return False

Your turn: LeetCode 438: Find All Anagrams in a String asks for every start index where an anagram of p begins in s. Both strings are non-empty and lowercase. Adapt check_inclusion, then predict the output for s = "cbaebabacd", p = "abc" and for s = "abab", p = "ab".

def find_anagrams(s, p):
    m = len(p)
    need = [0] * 26
    window = [0] * 26
    for ch in p:
        need[ord(ch) - ord('a')] += 1
    starts = []
    for right, ch in enumerate(s):
        window[ord(ch) - ord('a')] += 1
        if right >= m:
            window[ord(s[right - m]) - ord('a')] -= 1
        if window == need:
            starts.append(right - m + 1)   # window is s[right-m+1 .. right]
    return starts

print(find_anagrams("cbaebabacd", "abc"), find_anagrams("abab", "ab"))   # [0, 6] [0, 1, 2]

Final round: no label on the problem

Each challenge below uses one or two moves from this lesson. Decide which before you open the answer.

Challenge 1: the next bigger number

Given a positive 32-bit integer n, return the smallest integer that uses exactly the same digits and is bigger than n. If there is none, or if it does not fit in a signed 32-bit integer (at most 2,147,483,647), return −1. This is LeetCode 556: Next Greater Element III.

Predict the results for 12, 21, 230241, 2147483476 and 2147483647.

def next_greater_element(n):
    a = list(str(n))
    if not next_permutation(a):       # digits never rise: n is already the largest
        return -1
    m = int("".join(a))
    return m if m <= 2**31 - 1 else -1

print([next_greater_element(x) for x in (12, 21, 230241, 2147483476, 2147483647)])
# [21, -1, 230412, 2147483647, -1]

Challenge 2: palindromes only

Return every distinct palindrome you can make by rearranging s (at most 16 letters), in any order. aabb gives ["abba", "baab"] and abc gives []. This is LeetCode 267: Palindrome Permutation II.

Before you code it, work out one number. A 16-letter string with eight letters twice each has how many distinct arrangements? How many of them are palindromes?

from collections import Counter

def generate_palindromes(s):
    counts = Counter(s)
    odd = [ch for ch, c in counts.items() if c % 2 == 1]
    if len(odd) > 1:
        return []
    middle = odd[0] if odd else ""
    half = "".join(ch * (c // 2) for ch, c in counts.items())
    return [h + middle + h[::-1] for h in distinct_perms(half)]

print(generate_palindromes("aabb"), generate_palindromes("abc"), generate_palindromes("aabbc"))
# ['abba', 'baab'] [] ['abcba', 'bacab']

Challenge 3: three requests, one word

A puzzle app works with the word banana. It asks:

1. How many distinct words can be made from its letters?
2. Which word comes right after banana in dictionary order?
3. Which word is 30th in dictionary order?

Pick a move for each, as if the word had 30 letters and listing was impossible.

Cheat sheet

Before moving on, take aab and, from a blank editor, write the letter-bag generator, next_permutation, and the count window. For each one, say out loud what the key variable means at a specific moment: what bag holds before a call, why the suffix after the pivot is the largest arrangement of its letters, and which letters window counts after index right. Then name the one small edit that breaks each: a missing bag[ch] += 1, a > for >=, or right - m + 1 for right - m.

Next: Constraint Satisfaction turns "check before drawing" into a full toolkit (N-Queens, Sudoku, Word Search). String Algorithms moves from "some rearrangement appears" to finding exact patterns fast. For the general template, go back to Permutations & Combinations.