Facebook Pixel

3744. Find Kth Character in Expanded String 🔒

MediumString
LeetCode ↗
ProblemPatternIdeaExampleCodeComplexPitfalls

Problem Description

You are given a string s made up of one or more words, where each word is separated by a single space. Every word consists only of lowercase English letters.

From s, we build an expanded string t using the following rule:

  • For each word in s, we repeat its characters in increasing amounts based on their position. The first character appears 1 time, the second character appears 2 times, the third character appears 3 times, and so on.

For instance, if s = "hello world", then the expansion works as follows:

  • For the word "hello": h once, e twice, l three times, l four times, o five times, giving "heelllllllooooo".
  • For the word "world": w once, o twice, r three times, l four times, d five times, giving "woorrrllllddddd".

So the full expanded string becomes t = "heelllllllooooo woorrrllllddddd", where the spaces between words in s are preserved in t.

You are also given an integer k, which is guaranteed to be a valid index of the string t.

Your task is to return the character located at the kth position of the string t.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

How We Pick the Algorithm

Why Greedy Algorithms?

This problem maps to Greedy Algorithms through a short path in the full flowchart.

Computemax/min?yesGreedysolution?yesGreedyAlgorithms

Making the locally optimal decision at each step produces the globally optimal result.

Open in Flowchart

Intuition

The key observation is that we don't actually need to build the entire expanded string t to find the kth character. Building t could be very wasteful in both time and memory, especially when the words are long, since each character is repeated many times. Instead, we can figure out where the kth character falls by reasoning about the lengths of each expanded piece.

Let's think about how much space each word takes up in t. For a word w, the first character appears 1 time, the second 2 times, and so on up to |w| times. The total length contributed by this word is the sum 1 + 2 + ... + |w|, which by the formula for the sum of consecutive integers equals m = (1 + |w|) * |w| / 2.

Now we can walk through the words one by one, keeping track of how far k reaches into t. For each word, there are three possibilities:

  • If k lands exactly at position m (just past the end of the current word's expansion), then k points to the space separating this word from the next, so we return a space.
  • If k is greater than m, then the kth character lies somewhere beyond this word. We subtract this word's expanded length m plus 1 for the space, then move on to consider the next word with the updated k.
  • Otherwise, k falls within this word's expanded portion, so we need to locate exactly which original character it corresponds to.

For that last case, we simulate the expansion gradually. We keep a running total cur that accumulates how many expanded characters we've passed so far. For each character w[i], it contributes i + 1 copies, so we add i + 1 to cur. The moment k < cur, we know k falls inside the block of repeated w[i] characters, so w[i] is our answer.

This approach lets us jump straight to the right word and the right character using arithmetic, avoiding the cost of constructing the full string.

Solution Approach

Solution 1: Math + Simulation

We first split the string s into multiple words by spaces using s.split(). Then we process each word w in order, deciding whether the kth character falls within it.

For each word w, we compute the length it occupies in the expanded string t as m = (1 + len(w)) * len(w) // 2. This comes from the fact that the characters contribute 1 + 2 + ... + len(w) copies in total.

Next, we compare k against m to decide what to do:

  • If k == m, the kth character is the space that follows this word, so we directly return " ".
  • If k > m, the kth character is not inside this word's expanded portion. We update k by subtracting m + 1 (the m characters of this word's expansion plus the 1 space after it), then continue to the next word.
  • Otherwise, the kth character lies within this word's expanded portion, and we find it through simulation.

To locate the character inside the word, we use a running counter cur = 0 to track how many expanded characters we have accounted for so far. We iterate over each index i of the word:

  • Add i + 1 to cur, since the character w[i] is repeated i + 1 times.
  • If k < cur, then k falls inside the block of repeated w[i] characters, so we return w[i].

By using the arithmetic formula to skip over whole words and only simulating within the single relevant word, we avoid constructing the full expanded string.

In terms of complexity, the time complexity is O(n), where n is the length of the string s, since each character of s is examined at most a constant number of times. The space complexity is O(n) due to the list of words produced by the split operation.

Example Walkthrough

Let's trace through a small example to see how the solution finds the kth character without building the full expanded string.

Input: s = "abc de", k = 8

First, let's understand what the expanded string t looks like (just for our own verification — the algorithm never actually builds it):

  • For the word "abc": a once, b twice, c three times → "abbccc" (length 6)
  • For the word "de": d once, e twice → "dee" (length 3)

So t = "abbccc dee", and the positions are indexed as:

Index012345678
Charabbccc(space)de

We want the character at index k = 8, which we can see should be "e". Let's confirm the algorithm reaches the same answer.

Step 1: Split into words

s.split() gives us ["abc", "de"]. We process them in order with k = 8.

Step 2: Process the first word "abc"

Compute its expanded length:

m = (1 + len("abc")) * len("abc") // 2 = (1 + 3) * 3 // 2 = 6

Now compare k = 8 against m = 6:

  • Is k == m? 8 == 6 → No.
  • Is k > m? 8 > 6 → Yes. The kth character lies beyond this word.

So we skip this word entirely. We subtract its expanded length plus one for the following space:

k = k - (m + 1) = 8 - (6 + 1) = 1

Now k = 1, and we move on to the next word. Notice this new k = 1 is relative to the start of the second word's expansion "dee".

Step 3: Process the second word "de"

Compute its expanded length:

m = (1 + len("de")) * len("de") // 2 = (1 + 2) * 2 // 2 = 3

Compare k = 1 against m = 3:

  • Is k == m? 1 == 3 → No.
  • Is k > m? 1 > 3 → No.
  • Otherwise: k falls within this word's expanded portion. We simulate to find the exact character.

Step 4: Simulate inside "de"

Initialize cur = 0 and iterate over the indices of "de":

  • i = 0, character w[0] = 'd', repeated i + 1 = 1 time:
    • cur += 1 → cur = 1
    • Is k < cur? 1 < 1 → No. Keep going.
  • i = 1, character w[1] = 'e', repeated i + 1 = 2 times:
    • cur += 2 → cur = 3
    • Is k < cur? 1 < 3 → Yes. The answer is w[1] = 'e'.

Result: The character at index 8 is "e", which matches our manual check of t = "abbccc dee".

This demonstrates the two core ideas working together: arithmetic (m = (1 + len(w)) * len(w) // 2) lets us leap over the whole first word in one move, and lightweight simulation pinpoints the exact character inside only the single relevant word — never constructing the full string t.

Solution Implementation

1class Solution:
2    def kthCharacter(self, s: str, k: int) -> str:
3        # Process each whitespace-separated word independently.
4        for word in s.split():
5            length = len(word)
6            # Length of this word's expanded form:
7            # character word[i] is repeated (i + 1) times,
8            # so total length = 1 + 2 + ... + length = (1 + length) * length // 2.
9            expanded_len = (1 + length) * length // 2
10
11            # k lands exactly on the separator that follows this word's expansion.
12            if k == expanded_len:
13                return " "
14
15            # k points beyond this word (and its trailing separator):
16            # skip the whole expansion plus the single separator (expanded_len + 1).
17            if k > expanded_len:
18                k -= expanded_len + 1
19            else:
20                # k falls inside this word's expansion.
21                # Walk the cumulative block boundaries to find the matching character.
22                cumulative = 0
23                for i in range(length):
24                    cumulative += i + 1  # end boundary of the (i)-th character block
25                    if k < cumulative:
26                        return word[i]
27
28        # Fallthrough (unreachable for valid inputs); keeps a defined return.
29        return ""
30
1class Solution {
2    public char kthCharacter(String s, long k) {
3        // Process each word separated by spaces in the original string
4        for (String word : s.split(" ")) {
5            int len = word.length();
6
7            // Total characters this word contributes after triangular expansion:
8            // 1st char x1, 2nd char x2, ..., len-th char x len  => len*(len+1)/2
9            long expandedLength = (1L + len) * len / 2;
10
11            // If k lands exactly on the boundary right after this word,
12            // it points to the separating space character
13            if (k == expandedLength) {
14                return ' ';
15            }
16
17            if (k > expandedLength) {
18                // k is beyond this word (plus its trailing space),
19                // so skip this word's expanded length and the space (+1)
20                k -= expandedLength + 1;
21            } else {
22                // k falls within this word's expanded section.
23                // Accumulate counts (1, 2, 3, ...) until we pass k,
24                // then the current index i is the target character.
25                long cumulative = 0;
26                for (int i = 0; ; ++i) {
27                    cumulative += i + 1; // i-th char (0-indexed) appears i+1 times
28                    if (k < cumulative) {
29                        return word.charAt(i);
30                    }
31                }
32            }
33        }
34
35        // Fallback (k out of range); return space by default
36        return ' ';
37    }
38}
39
1class Solution {
2public:
3    char kthCharacter(string s, long long k) {
4        // Use a stream to split the input string into words by whitespace.
5        stringstream ss(s);
6        string word;
7
8        // Process each word's expanded representation in sequence.
9        while (ss >> word) {
10            // Length of the current word's expansion:
11            // character i (0-based) is repeated (i + 1) times,
12            // so the total length is 1 + 2 + ... + n = n * (n + 1) / 2.
13            long long expandedLen =
14                (1 + static_cast<long long>(word.size())) *
15                static_cast<long long>(word.size()) / 2;
16
17            // If k points exactly at the position right after this word's
18            // expansion, it falls on the separator space between words.
19            if (k == expandedLen) {
20                return ' ';
21            }
22
23            if (k > expandedLen) {
24                // k lies beyond this word; skip its expansion plus the
25                // following separator space (hence expandedLen + 1).
26                k -= expandedLen + 1;
27            } else {
28                // k lies within this word's expansion.
29                // Accumulate the triangular counts to locate the bucket.
30                long long prefix = 0;
31                for (int i = 0;; ++i) {
32                    // After this step, prefix covers characters 0..i,
33                    // where character i occupies (i + 1) positions.
34                    prefix += i + 1;
35                    if (k < prefix) {
36                        return word[i];
37                    }
38                }
39            }
40        }
41
42        // No matching character found (k is out of range).
43        return ' ';
44    }
45};
46
1/**
2 * Finds the k-th character (0-indexed) in a sequence built from a space-separated string.
3 *
4 * Each word `w` is conceptually expanded so that its i-th character (1-indexed)
5 * is repeated i times — e.g. "abc" -> "abbccc". The expanded length of a word
6 * of length n is the triangular number n*(n+1)/2. Words are joined by single
7 * space separators that also occupy one position in the sequence.
8 *
9 * @param s The input string of space-separated words.
10 * @param k The 0-indexed position to look up.
11 * @returns The character located at position k, or a space if it falls on a separator.
12 */
13function kthCharacter(s: string, k: number): string {
14    // Iterate over each word in the space-separated input.
15    for (const word of s.split(' ')) {
16        // Expanded length of this word (triangular number of its length).
17        const expandedLength = ((1 + word.length) * word.length) / 2;
18
19        // k lands exactly on the separator space that follows this word.
20        if (k === expandedLength) {
21            return ' ';
22        }
23
24        // k is beyond this word: skip the whole expanded word plus its separator.
25        if (k > expandedLength) {
26            k -= expandedLength + 1;
27        } else {
28            // k falls inside this word: accumulate per-character repetition counts.
29            let cumulativeCount = 0;
30            for (let index = 0; ; ++index) {
31                // Character at `index` (0-based) is repeated (index + 1) times.
32                cumulativeCount += index + 1;
33                if (k < cumulativeCount) {
34                    return word[index];
35                }
36            }
37        }
38    }
39
40    // k is out of range; default to a space.
41    return ' ';
42}
43

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the string s. The outer loop iterates over the words obtained from s.split(). For each word w, the code either computes m in O(1) time and updates k, or enters an inner loop that scans the characters of w taking O(len(w)) time. Since each character of s is processed at most once across all iterations (the split produces words whose total length is bounded by the length of s, and the inner scan only runs for a single word before returning), the overall work is linear in the length of s, giving O(n).

  • Space Complexity: O(n), where n is the length of the string s. The call to s.split() creates a list of words whose combined length is proportional to the length of s, requiring O(n) additional space. The remaining variables (m, k, cur, i) only use constant O(1) space, so the dominant term is O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Confusing 0-indexed and 1-indexed positions for k

The most common mistake is mishandling whether k is 0-indexed or 1-indexed, which directly affects every comparison in the code.

In the provided solution, k is treated as 0-indexed. This subtle convention drives three critical decisions:

  • The check if k == expanded_len (not k == expanded_len - 1) identifies the separator. With 0-indexing, valid character positions inside the word's expansion are 0 to expanded_len - 1, so position expanded_len is exactly the space.
  • The skip step k -= expanded_len + 1 accounts for expanded_len expanded characters (indices 0 to expanded_len - 1) plus the 1 separator.
  • The inner loop uses if k < cumulative because cumulative is a count (1-based size), while k is a 0-based index.

If k were instead 1-indexed, every comparison would need adjustment. A frequent error is to mix conventions—for example, using k == expanded_len for the separator but then writing if k <= cumulative in the inner loop, which causes an off-by-one error that returns the wrong character at block boundaries.

Solution: Decide the indexing convention up front and apply it consistently. If the problem states k is 1-indexed, normalize it immediately:

class Solution:
    def kthCharacter(self, s: str, k: int) -> str:
        k -= 1  # normalize 1-indexed input to 0-indexed
        for word in s.split():
            length = len(word)
            expanded_len = (1 + length) * length // 2
            if k == expanded_len:
                return " "
            if k > expanded_len:
                k -= expanded_len + 1
            else:
                cumulative = 0
                for i in range(length):
                    cumulative += i + 1
                    if k < cumulative:
                        return word[i]
        return ""

Pitfall 2: Building the full expanded string t

A naive approach constructs the entire expanded string and indexes into it:

# Inefficient and memory-heavy
t = " ".join("".join(c * (i + 1) for i, c in enumerate(w)) for w in s.split())
return t[k]

While correct, this can be problematic. A word of length L expands to (1 + L) * L // 2 characters—quadratic growth relative to the word length. For long words, this consumes far more memory than necessary, since you only need a single character.

Solution: Use the arithmetic formula to skip whole words in O(1) per word, and only simulate within the single relevant word. This keeps memory proportional to the input s (from the split), not the much larger expansion t.

Pitfall 3: Forgetting that separators occupy positions in t

The spaces between words are preserved in t and therefore occupy valid indices. A common error is to skip only expanded_len characters when moving past a word:

# Wrong: ignores the separator
if k > expanded_len:
    k -= expanded_len   # should be expanded_len + 1

This omission causes the index to drift by one for every word boundary crossed, returning incorrect results for any k that lands in the second word or later.

Solution: Always subtract expanded_len + 1 when skipping a word, accounting for both the expansion and its trailing separator. Note that the very last word has no trailing separator, but since k is guaranteed valid, control never reaches a non-existent separator beyond the final word.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Depth first search is equivalent to which of the tree traversal order?

Recommended Readings

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Explained

Recursion If you prefer videos here's a video that explains recursion in a fun and easy way Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask him

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity describes how the time needed

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More