I liked this problem. It's straightforward enough to be an Easy but leaves room for a clean, single-pass, in-place solution. I dislike the hints since they promote an inelegant implementation, but linear is linear, and time complexity is the main metric Leetcode tests.

Copied!python3
1class Solution:
2    def findKDistantIndices(self, nums: List[int], key: int, k: int) -> List[int]:
3        length = len(nums)
4        stop = -1
5        j = 0
6        for i in range(-k, length):
7            if i + k < length and nums[i + k] == key:
8                stop = i + (k << 1)
9            if i >= 0 and i <= stop:
10                nums[j] = i
11                j += 1
12        del nums[j:]
13        return nums

I considered making stop an exclusive index initialized to 0 (negative initializations are ugly), but that would have required an extra + 1 on line 8.

Now is NOT a good time for a Hard. I already spent all night on this blog.

😔

Anyways, the problem seemed doable at first. Heck, I understood the assignment in just a few minutes. Record time!

Then I realized numbers could be negative. Yikes.

Yikes.

That was bad. And not the good kind of bad that tickles your brain until you find an elegant, linear-time solution. I was hoping I could pick the next smallest product at every step.

Copied!python3
1# Results of incrementing each idx
2cand = [
3    nums1[idx[0] + 1] * nums2[idx[1]] if idx[0] + 1 < lim[0] else MAX,
4    nums1[idx[0]] * nums2[idx[1] + 1] if idx[1] + 1 < lim[1] else MAX,
5    nums1[idx[2] + 1] * nums2[idx[3]] if idx[2] + 1 < lim[2] else MAX,
6    nums1[idx[2]] * nums2[idx[3] + 1] if idx[3] + 1 < lim[3] else MAX,
7]

It was a binary search. I hate binary searches.

They show up in the most random places, no matter the size of the search space. Verifying a condition from -10¹⁰ to 10¹⁰ is practically brute force.

I suspected the solution would be a binary search on the output value, but I started with other approaches in hopes of something nicer. No dice, but at least sign tracking proved relevant, and my sign_cutoff function was transferable.

Unfortunately, the verification function contained edge cases galore. I guess that should be expected of a Hard. But you know it's bad when I pull out the local editor.

Copied!python3
1class Solution:
2    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:
3        len1 = len(nums1)
4        len2 = len(nums2)
5
6        def sign_cutoff(nums):
7            # Returns index of first nonnegative number
8            left, right = 0, len(nums) - 1
9            while left < right:
10                mid = (left + right) // 2
11                if nums[mid] < 0:
12                    left = mid + 1
13                else:
14                    right = mid
15
16            if nums[left] >= 0:
17                return left
18            return len(nums)
19
20        sc1 = sign_cutoff(nums1)
21        sc2 = sign_cutoff(nums2)
22        i = sc1
23        while i < len1 and nums1[i] == 0:
24            i += 1
25        z1 = i - sc1 # number of zeros
26        j = sc2
27        while j < len2 and nums2[j] == 0:
28            j += 1
29        z2 = j - sc2 # number of zeros
30        nzero = z1 * len2 + z2 * len1 - z1 * z2
31        nneg = sc1 * (len2 - sc2 - z2) + sc2 * (len1 - sc1 - z1)
32
33        print(f'{sc1=} {z1=} {sc2=} {z2=} {nneg=} {nzero=}')
34
35        def prods_leq(limit):
36            # Returns the number of products less than or equal to limit
37            if limit == 0:
38                return nneg + nzero
39
40            if limit > 0:
41                nless = nneg + nzero
42                # i < 0, j < 0
43                j = 0
44                for i in range(sc1 - 1, -1, -1):
45                    while j < sc2 and nums1[i] * nums2[j] > limit:
46                        j += 1
47                    nless += sc2 - j
48                # i > 0, j > 0
49                j = len2 - 1
50                for i in range(sc1 + z1, len1):
51                    while j >= sc2 + z2 and nums1[i] * nums2[j] > limit:
52                        j -= 1
53                    nless += j - (sc2 + z2) + 1
54                return nless
55
56            nless = 0
57            # i < 0, j > 0
58            j = sc2 + z2
59            for i in range(sc1):
60                while j < len2 and nums1[i] * nums2[j] > limit:
61                    j += 1
62                nless += len2 - j
63            # i > 0, j < 0
64            j = 0
65            for i in range(sc1 + z1, len1):
66                while j < sc2 and nums1[i] * nums2[j] <= limit:
67                    j += 1
68                nless += j
69            return nless
70
71        left, right = -10 ** 10, 10 ** 10
72        while left < right:
73            mid = (left + right) // 2
74            if prods_leq(mid) >= k:
75                right = mid
76            else:
77                left = mid + 1
78        return left
Show More

Certainly not my best code. Most logic occurs in prods_leq. There's probably some symmetry there that I screwed up. I encountered so many off-by-one errors that by the end, I had accumulated 7/8 testcases.

Maybe f*#! around and find out was not the right approach.

The editorial solution is much shorter but has worse time complexity. It uses a binary search to determine the j corresponding to each i.

I considered adding early-out conditions and merging some cases, but I'm too tired at this point.

This problem was a relief after yesterday's... event. I'd place it on the easier end of Medium problems. Two edge cases threw me for a loop (the two if statements below), but solving otherwise went smoothly.

Copied!python3
1class Solution:
2    def longestSubsequence(self, s: str, k: int) -> int:
3        length = len(s)
4        k = bin(k)[2:]
5        out = len(k)
6        if out > length:
7            return length
8        if s[length - out:] > k:
9            out -= 1
10        out += s[:length - out].count('0')
11        return out

I initially used string indexing but later refactored to slicing. I'll trade memory for elegance any day.

Copied!C
1int longestSubsequence(char* s, int k) {
2    int out = 32 - __builtin_clz(k);
3    int length = strlen(s);
4    if (out > length) {
5        return length;
6    }
7    char* endptr;
8    if (strtol(s + length - out, &endptr, 2) > k) {
9        out--;
10    }
11    int stop = length - out;
12    for (int i = 0; i < stop; i++) {
13        if (s[i] == '0') {
14            out++;
15        }
16    }
17    return out;
18}

To feel better about Python's gratuitous copying of string slices, I ported my logic to C.

This Hard caught me a little off guard. We had one two days ago. I was expecting a Medium.

Anyways, I loved this problem! It made me feel so, so clever. After racking my brain for days on end, I happened upon my greatest insight...

* drumroll *

In particular, the constraint that n < k * 8. I hope sarcasm has conveyed my utter disappointment. They got my hopes up with the topics list. I love Greedy problems.

Luckily, prior analysis had tempered my expectations. I had already considered the situation where s = abccaccb and k = 2. The subsequence ab works but is not necessarily a prefix of the longest subsequence. Even now, I'm not entirely sure why Greedy was on there.

Back to the insight. Here are some comments I made:

Copied!python3
1# n is at most 8 * k
2# ss is at most 8 characters
3# 256 * length time complexity
4# linear!

I also made the faulty assumption that the longest subsequence would be contained within the first n // k characters, but regardless, I discovered that the solution would be brute force. Hooray!

The assumption actually worked quite well. With n // k changed to ceil(n / k), my program passed 304 / 313 testcases. Note that n here is the number of characters in s occurring at least k times. With the subsequence search space expanded to the first 2 * n // k characters, my program passed 312 / 313 testcases.

At this point, any sane person would just hardcode the 313th test.

I decided to be a sane person. Don't tell Leetcode.

Runtime beat 46.34%. Memory beat 36.59%. Blending right in!

Anyways, the assumption proved faulty because the first occurrence of a subsequence can extend deep into s while remaining occurrences bunch up at the end. Use of the proper search space led to Time Limit Exceeded.

I took a short break from the problem, but the various loopholes didn't sit right with me, so I eventually went back to the drawing board. Sorry to disappoint.

I promise I have a life.
I promise I have a life.
I do not promise I have a sleep schedule.

Luckily, most of my code was reusable, and I thought of switching to a character bank relatively quickly.

Copied!python3
1class Solution:
2    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
3        # Only care about characters that appear at least k times
4        cnt = Counter(s)
5        new_s = ''
6        for c in s:
7            if cnt[c] >= k:
8                new_s += c
9        s = new_s
10        length = len(s)
11
12        def is_valid(ss):
13            # Determines if ss occurs k times in s
14            idx, completed = 0, 0
15            sslen = len(ss)
16            remaining = sslen * k
17            for i, c in enumerate(s):
18                if c == ss[idx]:
19                    idx += 1
20                    remaining -= 1
21                    if idx == sslen:
22                        idx = 0
23                        completed += 1
24                        if completed == k:
25                            return True
26                if remaining >= length - i:
27                    return False
28            return completed == k
29
30        ssbank = {char: n // k for char, n in cnt.items()}
31        maxlen = length // k
32        valid = []
33
34        def dfs(ss, bestlen):
35            if len(ss) == maxlen:
36                return bestlen
37            for c in ssbank:
38                if ssbank[c]:
39                    ssbank[c] -= 1
40                    ss += c
41                    if is_valid(ss):
42                        if len(ss) >= bestlen:
43                            valid.append(ss)
44                            bestlen = len(ss)
45                        bestlen = dfs(ss, bestlen)
46                    ss = ss[:-1]
47                    ssbank[c] += 1
48            return bestlen
49
50        bestlen = dfs('', 0)
51
52        if valid:
53            return max(filter(lambda ss: len(ss) >= bestlen, valid))
54
55        return ''
Show More

The program uses a depth-first search to construct and validate subsequences. If a subsequence fails, I kill off its bloodline.

There's probably a technical term for that, but violence is more fun.

The editorial solution is actually quite elegant. Turns out my is_valid was much more verbose than necessary. Swapping it for the editorial one-liner brought my runtime from 52.03% to 95.12%. Yay generators. The editorial also opts for a nice, queue-based breadth-first search. I'll paste it below for those too lazy to find it.

Copied!python3
1class Solution:
2    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
3        ans = ""
4        candidate = sorted(
5            [c for c, w in Counter(s).items() if w >= k], reverse=True
6        )
7        q = deque(candidate)
8        while q:
9            curr = q.popleft()
10            if len(curr) > len(ans):
11                ans = curr
12            # generate the next candidate string
13            for ch in candidate:
14                nxt = curr + ch
15                it = iter(s)
16                if all(ch in it for ch in nxt * k):
17                    q.append(nxt)
18        return ans

I am now ashamed of my line count.

In the end, I didn't find this problem that bad. The big insight was still exciting given my prior state, head.empty. I certainly enjoyed this problem more than Wednesday's, though Wednesday was a very low bar.

Nevertheless, problems governed by testcase constraints feel a little pointless. Though real-world problems can (and often do) have constraints, succumbing to brute force because it *passes the tests* is boring and bound to disappoint.

Finally an Easy. This problem was alright, though with Python 3, it mostly just tests how well you know your builtins. I brainstormed some very ugly ideas to deal with repeats (one involved a Counter), but luckily, those never saw the light of day. I wrote two solutions: one that just sorts and one that uses a heap.

Copied!python3
1class Solution:
2    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
3        top = sorted([(n, i) for i, n in enumerate(nums)])[-k:]
4        top.sort(key=lambda ni: ni[1])
5        return [ni[0] for ni in top]

Heap syntax is so cursed in Python 3. And there's no max heap. At least this problem didn't require one.

Copied!python3
1class Solution:
2    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
3        top = []
4        heapify(top)
5        for i, n in enumerate(nums):
6            if i < k:
7                heappush(top, (n, i))
8            else:
9                heappushpop(top, (n, i))
10        top.sort(key=lambda ni: ni[1])
11        return [ni[0] for ni in top]

Have a Rust solution too!

Copied!rust
1impl Solution {
2    pub fn max_subsequence(nums: Vec<i32>, k: i32) -> Vec<i32> {
3        let length = nums.len();
4        let mut sorted = nums.into_iter().enumerate().collect::<Vec<(_, _)>>();
5        sorted.sort_by_key(|it| it.1);
6        let top = &mut sorted[length - k as usize..length];
7        top.sort_unstable();
8        top.into_iter().map(|it| it.1).collect()
9    }
10}

The Rust implementation was meant to take ten minutes. Unfortunately, I forgot that Rust syntax isn't nearly as straightforward as Python syntax. Remind me to use an actual editor next time I'm feeling masochistic.

Also, I love functional programming in Rust, but sorting ruins everything.

This problem was good but pretty hard for me. Although I found the approach almost immediately, I struggled with implementation. I couldn't decide whether to make i and j inclusive or exclusive and whether to start them at the center or edges. At one point, there was even a k. And naturally, I had several off-by-one errors.

Leetcode problems have ingrained in me a phobia of repeated numbers, so I also spent a while considering how my program would respond to them. My apprehension led to various while loops and lots of pain. I got rid of them after debugging the default tests though.

Copied!python3
1while i + 1 < length and nums[i] == nums[i + 1]:
2    i += 1

For a while, my program was passing testcases 1-19 but failing on the 20th. Intermediate failures almost always result from Time Limit Exceeded or edge cases, so when nothing about the test jumped out at me, I figured the bug must be related to repeated numbers.

Copied!text
1[14,4,6,6,20,8,5,6,8,12,6,10,14,9,17,16,9,7,14,11,14,15,13,11,10,18,13,17,17,14,17,7,9,5,10,13,8,5,18,20,7,5,5,15,19,14]
222

With repeats removed, the test passed. Ergo repeats were the problem.

I thought.

Well anyways, I proceeded to pull out my iPad (whoa) to painstakingly review my logic. This bug was particularly difficult to catch because the modulo system prevented me from knowing whether my program was undercounting or overcounting.

Undercounting or overcounting. Wanna take a guess?

3... 2... 1...

But Alex! How could that possibly be???

Because I'm stupid. That's how. Brain? We don't do that here.

Copied!python3
1class Solution:
2    def numSubseq(self, nums: List[int], target: int) -> int:
3        MOD = 10 ** 9 + 7
4        length = len(nums)
5        nums.sort()
6        j = bisect_right(nums, target // 2)
7        i = j - 1
8        delta = 1
9        out = 0
10        while i >= 0:
11            while j < length and nums[i] + nums[j] <= target:
12                delta = delta * 2 % MOD
13                j += 1
14            out = (out + delta) % MOD
15            i -= 1
16            delta = delta * 2 % MOD
17        return out

Guess what! If the problem specifies that your answer should be taken modulo 10⁹ + 7, then your answer should probably be less than 10⁹ + 7.

So anyways, it took over half an hour to realize that line 14 needed a MOD as well. The testcase output highlighted that most of my digits were matching, but at the time, I explained it away as pure coincidence.

Repeated numbers ultimately required no special treatment, but hey, delusion and suffering are essential components of the Leetcode grind.

This problem was pretty straightforward. My original plan was to sort nums and make some state variables, but then I realized a Counter implementation would probably be easier.

Copied!python3
1class Solution:
2    def findLHS(self, nums: List[int]) -> int:
3        cnt = Counter(nums)
4        return max(cl + (cnt[nl + 1] if nl + 1 in cnt else -cl) for nl, cl in cnt.items())

My submission scored 65.29% on runtime. Ewww. Disowned.

Copied!python3
1class Solution:
2    def findLHS(self, nums: List[int]) -> int:
3        nums.sort()
4        num_prev, cnt_prev = nums[0], 0
5        num_curr, cnt_curr = nums[0], 0
6        best = 0
7        for num in nums:
8            if num == num_curr:
9                cnt_curr += 1
10                continue
11            if num_curr == num_prev + 1 and cnt_curr + cnt_prev > best:
12                best = cnt_curr + cnt_prev
13            num_prev, cnt_prev = num_curr, cnt_curr
14            num_curr, cnt_curr = num, 1
15        if num_curr == num_prev + 1 and cnt_curr + cnt_prev > best:
16            best = cnt_curr + cnt_prev
17        return best

This fella scored 96.80%. Hooray!

But then I reran the program and received a lukewarm 56.05%. Three times over.

I also copied several top submissions and ran them myself. They scored pretty average. Moral of the story? Always take Leetcode percentiles with a grain of salt, especially on Easy problems.

Alternatively, claim really really confidently that you are the best, and your dreams just might come true.

Copied!python3
1# Nothing to see here
2__import__('atexit').register(lambda: open('display_runtime.txt', 'w').write('0'))

This problem was probably the easiest so far. I brainstormed the solution immediately. The only edit I had to make was adding 1 for the case where Alice doesn't make a typo.

On a side note, it was fun for the problem to have a premise. I wonder why Alice is typing abbcccc though.

Copied!python3
1class Solution:
2    def possibleStringCount(self, word: str) -> int:
3        return 1 + sum(word[i] == word[i + 1] for i in range(len(word) - 1))

Copied!python3
1class Solution:
2    def possibleStringCount(self, word: str) -> int:
3        it = iter(word)
4        next(it)
5        return 1 + sum(f == l for f, l in zip(it, iter(word)))

Copied!python3
1class Solution:
2    def possibleStringCount(self, word: str) -> int:
3        out = 1
4        for i in range(len(word) - 1):
5            if word[i] == word[i + 1]:
6                out += 1
7        return out

Copied!python3
1class Solution:
2    def possibleStringCount(self, word: str) -> int:
3        prev = None
4        out = 1
5        for c in word:
6            if c == prev:
7                out += 1
8            prev = c
9        return out

I tried four solutions in hopes of better runtime, though as we learned yesterday, runtime is a lie. I think it's a bit absurd that the sample below has the top performance.

Copied!python3
1class Solution:
2    def possibleStringCount(self, word: str) -> int:
3
4        stack = []
5
6        ans = 1 
7
8        for w in word:
9            if not stack or (stack and w==stack[-1]):
10                stack.append(w)
11            else:
12                ans+=len(stack)-1
13                stack = [w]
14            
15            #print(w,stack,ans)
16
17        ans+=len(stack)-1
18        
19
20
21
22        return ans
Show More

Why the list bro.

Sit tight. I've got lots to talk about.

Of the Hard problems I've covered, this was probably my favorite. Not that there's been much competition. The other problems were all brute force. This problem actually required some thinking. Did I have a clue what was going on? Nope! But at least I had the opportunity to apply some logic and play with numbers.

Anyways, my first approach was a combinatorial solution. Something like stars and bars but with added restrictions. I spent a while pondering but gave up after reading the topics. Math was sadly absent. Some progress was transferable though, namely the logic to parse word into counts and the underlying goal of the problem. Some of my notes are below.

Copied!python3
1# all single letters are fixed, we can ignore them
2# we now have sets of double or triple letters
3# and some limit length - k of how many we can delete
4# don't care about the actual letters - just maintain counts
5# require one from each set - just subtract 1 from each count

Line 3 was a dire mistake.

Copied!python3
1# a1 + a2 + ... + an <= limit
2# 0 <= a1 <= l1, 0 <= a2 <= l2, ...

My second approach used memoization. I had seen Dynamic Programming under the topics but had no idea where to start and figured memoization would be easier. Implementation actually went quite smoothly. I had high hopes for a speedy completion.

Unfortunately, Leetcode is never that easy. I hit Time Limit Exceeded at 814/846 testcases. I'm not entirely sure why my code was failing. My best guesses are faulty memoization, too many stack frames, or the line 3 situation to be discussed shortly.

Regardless, I shifted gears to Dynamic Programming.

I think the switch would have been much smoother had I taken the time to fully understand my memoized approach. But I was impatient.

Most of my brainstorming revolved around a 2D array where rows corresponded to removal limits and column corresponded to cumulative groups of the counts array.

Copied!python3
1# ways[lim][idx] is the number of ways to delete up to lim
2# characters from counts 0 to idx, inclusive
3# NVM DONT DO THIS
4
5# ways[lim][idx] is the number of ways to satisfy limit
6# using characters from counts 0 to idx, inclusive
7# where the amount we remove at idx is lim

Guess which approach I ultimately went with.

If you guessed wrong, you must be new here. Welcome! Nothing makes sense. Escape while you still can.

After bouncing between approaches, drawing some useless diagrams, rereading my memoized implementation, and I kid you not, looking for patterns between iterations in my print statement output, I finally got Dynamic Programming to work.

Now guess the result.

Good work! You're learning.

This result was actually surprising though. My approach felt efficient enough. It had approximately quadratic time complexity, specifically

where $n$ is the length of word. I wasn't even using the 2D array anymore, just two 1D arrays.

Wait a minute.

Is it time for another 𝓰𝓻𝓮𝓪𝓽𝓮𝓼𝓽 𝓲𝓷𝓼𝓲𝓰𝓱𝓽?

Well f*#!. I've been counting removals on the order of $n - k$. To pass, I need to count inclusions on the order of $k$. Because that's what Leetcode tests for.

Hey, let's start a list: the Laws of Leetcode.

• Runtime is fake.
• Read the damn constraints.

These laws of course only apply when convenient. If I score 100% on runtime, then runtime is a wonderful metric.

Back to the problem. I had to completely redo my implementation, counting the opposite quantity. Hooray for pain and suffering.

🫠

But then I realized: all my program needed was a little shift in mindset. I declared that my arrays would count inclusions, not removals. Nobody objected! Me, myself, and I were all in agreement.

Essentially, if you know (1) the number of ways to include less than limit characters and (2) the total number of combinations of characters, you can subtract to find the number of ways to include at least limit characters.

The total combinations of characters is just the product of all counts in the counts array, though the modulo system makes multiplying a little annoying. I wanted to use prod so badly. Alas, we must accomodate the poor children still working in C.

Luckily, I only had to modify 7 lines to get my implementation working, though the resultant hodgepodge was quite the eyesore.

Copied!python3
1class Solution:
2    def possibleStringCount(self, word: str, k: int) -> int:
3        MOD = 10 ** 9 + 7
4        length = len(word)
5        if k >= length:
6            return 1
7        prev = None
8        count = 0
9        counts = []
10        for c in word:
11            if c == prev:
12                count += 1
13                continue
14            if count > 1:
15                counts.append(count - 1)
16            prev = c
17            count = 1
18        if count > 1:
19            counts.append(count - 1)
20        limit = k - (length - sum(counts)) - 1
21
22        total = 1
23        for count in counts:
24            total = total * (count + 1) % MOD
25
26        if limit < 0:
27            return total
28        unique = len(counts)
29        
30        prev = list(range(1, counts[0] + 1)) + [counts[0] + 1] * (limit + 1 - counts[0])
31
32        for idx in range(1, unique):
33            curr = [0] * len(prev)
34            curr[0] = 1
35            for lim in range(1, limit + 1):
36                curr[lim] = curr[lim - 1] + prev[lim]
37                if lim > counts[idx]:
38                    curr[lim] -= prev[lim - counts[idx] - 1]
39                curr[lim] %= MOD
40            prev = curr
41
42        return (total - prev[limit]) % MOD
Show More

It sure has personality!

Impressively, it scored 100.00% on runtime and 94.12% on memory. I challenged myself to clean up the implementation though. I managed to reduce the line count by 30%.

Copied!python3
1class Solution:
2    def possibleStringCount(self, word: str, k: int) -> int:
3        MOD = 10 ** 9 + 7
4        if k >= len(word):
5            return 1
6        limit = k - len(word)
7        prev = None
8        count = 0
9        counts = []
10        for c in word + '\0':
11            if c == prev:
12                count += 1
13                continue
14            if count > 1:
15                counts.append(count)
16                limit += count - 1
17            prev = c
18            count = 1
19
20        total = reduce(lambda tot, count: tot * count % MOD, counts)
21        if limit <= 0:
22            return total
23        
24        ways = [1] * limit
25        for count in counts:
26            ways = list(accumulate(ways))
27            for lim in reversed(range(count, limit)):
28                ways[lim] -= ways[lim - count]
29
30        return (total - ways[limit - 1]) % MOD
Show More

The refactored program has a runtime around 700 ms. For reference, my hodgepodge took around 1100 ms.

I also tested out numpy. Unfortunately, import statements tank the memory score, but the following program got down to 524 ms.

Copied!python3
1from numpy import ones, cumsum, int32
2
3class Solution:
4    def possibleStringCount(self, word: str, k: int) -> int:
5        MOD = 10 ** 9 + 7
6        if k >= len(word):
7            return 1
8        limit = k - len(word)
9        prev = None
10        count = 0
11        counts = []
12        for c in word + '\0':
13            if c == prev:
14                count += 1
15                continue
16            if count > 1:
17                counts.append(count)
18                limit += count - 1
19            prev = c
20            count = 1
21
22        total = reduce(lambda tot, count: tot * count % MOD, counts)
23        if limit <= 0:
24            return total
25        
26        ways = ones(limit, dtype=int32)
27        for count in counts:
28            ways = cumsum(ways) % MOD
29            ways[count:] -= ways[:-count]
30
31        return (total - ways[limit - 1]) % MOD
Show More

I'm not entirely sure why the subtractions work, but they do, and that's all that really matters. It's 7 AM. I'm going to sleep.

It's the following afternoon. I decided to actually understand what my solution was doing. Just thought I would share my notes here.

I also rewrote the program in Rust. The operation took much longer than anticipated. The modulo requirement isn't so bad in Python because Python just takes care of overflow errors and the modulo operator does what I expect.

In Rust, % isn't the same modulo operator. It can return negative numbers. In addition, 10⁹ + 7 is actually very close the the i32 limit. Debugging took a while since Leetcode disables overflow errors, and for the longest time, I couldn't tell why behavior was differing. I had to add modulo operations in several places for the program to work.

Copied!rust
1const MOD: i64 = 1_000_000_007;
2
3impl Solution {
4    pub fn possible_string_count(word: String, k: i32) -> i32 {
5        if k >= word.len() as i32 {
6            return 1;
7        }
8        let mut limit = k - word.len() as i32;
9        let mut prev = word.chars().next().unwrap();
10        let mut count = 1;
11        let mut counts = Vec::new();
12        for c in word.chars().skip(1).chain(std::iter::once('\0')) {
13            if c == prev {
14                count += 1;
15                continue;
16            }
17            if count > 1 {
18                counts.push(count);
19                limit += count - 1;
20            }
21            prev = c;
22            count = 1;
23        }
24        let total = counts.iter().fold(1i64, |acc, &count| acc * (count as i64) % MOD) as i32;
25        if limit <= 0 {
26            return total;
27        }
28        let mut ways = vec![1; limit as usize];
29        counts.iter().for_each(|&count| {
30            for i in 1..limit as usize {
31                ways[i] = (ways[i] + ways[i - 1]) % MOD as i32;
32            }
33            for i in (count..limit).rev() {
34                ways[i as usize] = (ways[i as usize] - ways[(i - count) as usize]) % MOD as i32;
35            }
36        });
37        (total - ways[limit as usize - 1]).rem_euclid(MOD as i32)
38    }
39}
Show More

Not the prettiest code, but it's good enough.

Globally caching the answer probably wasn't the intended solution, but I was feeling lazy. The actual solution probably involves operations on powers of 2.

Copied!python3
1word = "a"
2shift = lambda c: 'a' if c == 'z' else chr(ord(c) + 1)
3while len(word) < 500:
4    word += ''.join(map(shift, word))
5
6class Solution:
7    def kthCharacter(self, k: int) -> str:
8        return word[k - 1]