LeetCode 3744 - Find Kth Character in Expanded String

The problem gives us a string s containing one or more lowercase words separated by single spaces. From this original string, we conceptually build a new string t using a special expansion rule.

leetcodemediumstring

LeetCode Problem 3744

Difficulty: 🟡 Medium
Topics: String

Solution

LeetCode 3744 - Find Kth Character in Expanded String

Problem Understanding

The problem gives us a string s containing one or more lowercase words separated by single spaces. From this original string, we conceptually build a new string t using a special expansion rule.

For each word, the first character appears once, the second character appears twice, the third character appears three times, and so on. Spaces between words remain as single spaces in the expanded string.

For example:

Word: hello

h -> repeated 1 time  -> h
e -> repeated 2 times -> ee
l -> repeated 3 times -> lll
l -> repeated 4 times -> llll
o -> repeated 5 times -> ooooo

Expanded word: heelllllllooooo

For the input:

s = "hello world"

the expanded string becomes:

t = "heelllllllooooo woorrrllllddddd"

We are given an index k, and we must return the character located at position k in the expanded string t.

The important observation is that the constraints allow:

1 <= s.length <= 100000

This means the expanded string can become much larger than the original string. If a word has length m, its expanded length is:

1 + 2 + 3 + ... + m

which equals:

m(m + 1) / 2

For large words, explicitly constructing the entire expanded string may be unnecessarily expensive.

The problem guarantees that:

0 <= k < t.length

so the requested position always exists.

Important edge cases include a single-character word, strings containing only one word, positions that land exactly on a space between words, and positions that fall inside large repeated blocks of a character.

Approaches

Brute Force

The most direct solution is to actually construct the expanded string.

We scan each word. For the character at position i within the word, we append that character i + 1 times. Between words, we append a single space.

After building the complete expanded string t, we simply return:

t[k]

This approach is obviously correct because it exactly follows the definition of the expansion process.

The drawback is that the expanded string may become much larger than the input. Creating and storing the entire string costs time proportional to the size of the expanded result and requires the same amount of memory.

Optimal Approach

The key observation is that we do not need the entire expanded string. We only need the character at one position.

Instead of constructing t, we can walk through the original string and keep track of how many characters the expansion contributes.

For a word:

c0 c1 c2 ...

the expanded blocks have lengths:

1, 2, 3, ...

As we process each character, we know exactly how many positions it occupies in the expanded string.

Suppose the current character contributes a block of length len.

If:

k < len

then the desired position lies inside this block, so that character is the answer.

Otherwise, we subtract:

k -= len

and continue searching.

Spaces are handled similarly. Each space contributes exactly one character to the expanded string.

By consuming portions of k as we traverse the original string, we locate the answer without ever constructing the expanded result.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O( t )
Optimal O(n) O(1) Scans original string only, no expansion stored

Here, n = len(s).

Algorithm Walkthrough

  1. Initialize a pointer i = 0 to scan the original string.
  2. While i is within the string:

  • If s[i] is a space:

  • The expanded string contributes exactly one character.

  • If k == 0, return the space.

  • Otherwise decrement k by one and continue.

  1. If s[i] starts a word:
  • Record the start of the word.
  • Traverse the word character by character until a space or the end of the string is reached.
  1. For each character inside the word:
  • Let its position within the word be pos, starting from 0.
  • Its expansion length is:
pos + 1
  • If:
k < pos + 1

then the desired index falls inside this repeated block, so return that character.

  • Otherwise subtract:
k -= (pos + 1)

and continue. 5. Continue processing words and spaces until the answer is found. 6. The problem guarantees that k is valid, so a character will always be returned.

Why it works

At every step, k represents the position we still need to locate within the remaining unprocessed portion of the expanded string. Whenever we skip a block of length L, subtracting L from k removes exactly those positions from consideration. When k becomes smaller than the current block length, the target index must lie inside that block, and since every position in the block contains the same character, returning that character is correct.

Python Solution

class Solution:
    def kthCharacter(self, s: str, k: int) -> str:
        n = len(s)
        i = 0

        while i < n:
            if s[i] == ' ':
                if k == 0:
                    return ' '
                k -= 1
                i += 1
                continue

            position_in_word = 0

            while i < n and s[i] != ' ':
                block_length = position_in_word + 1

                if k < block_length:
                    return s[i]

                k -= block_length
                position_in_word += 1
                i += 1

        return ""

Implementation Explanation

The algorithm scans the original string exactly once.

Whenever a space is encountered, it contributes a single character to the expanded string. If the desired position is that space, we return it immediately. Otherwise we decrement k and continue.

For characters inside a word, we track their index within that word using position_in_word. A character at position p expands into a block of length p + 1.

Before skipping the block, we check whether the remaining target index k falls inside it. If it does, that character is the answer. Otherwise we subtract the block length from k and move forward.

Because we never build the expanded string, the solution uses constant extra memory.

Go Solution

func kthCharacter(s string, k int64) byte {
	n := len(s)
	i := 0

	for i < n {
		if s[i] == ' ' {
			if k == 0 {
				return ' '
			}
			k--
			i++
			continue
		}

		positionInWord := int64(0)

		for i < n && s[i] != ' ' {
			blockLength := positionInWord + 1

			if k < blockLength {
				return s[i]
			}

			k -= blockLength
			positionInWord++
			i++
		}
	}

	return 0
}

Go-Specific Notes

The Go signature uses int64 for k, so all arithmetic involving block lengths is also performed using int64 to avoid unnecessary conversions.

The algorithm itself is identical to the Python version. Since the input contains only lowercase English letters and spaces, indexing the string by byte is safe and efficient.

Worked Examples

Example 1

s = "hello world"
k = 0

Expanded string:

heelllllllooooo woorrrllllddddd
^

Processing:

Character Block Length k Before Result
h 1 0 0 < 1, return 'h'

Answer:

"h"

Example 2

s = "hello world"
k = 15

Processing the first word:

Character Block Length k Before k After
h 1 15 14
e 2 14 12
l 3 12 9
l 4 9 5
o 5 5 0

The first word contributes:

1 + 2 + 3 + 4 + 5 = 15

positions.

Next character is the space:

Character Block Length k Before
space 1 0

Since k == 0, return the space.

Answer:

" "

Additional Example

s = "abc"
k = 4

Expansion:

abbccc

Processing:

Character Block Length k Before k After
a 1 4 3
b 2 3 1
c 3 1 inside block

Answer:

'c'

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character of the original string is visited once
Space O(1) Only a few variables are used

The algorithm never constructs the expanded string. Instead, it directly determines which expansion block contains the requested index. Since every character of the original input is processed at most once, the running time is linear in the length of s, and the extra memory usage remains constant.

Test Cases

sol = Solution()

assert sol.kthCharacter("hello world", 0) == "h"      # first example
assert sol.kthCharacter("hello world", 15) == " "     # space between words

assert sol.kthCharacter("a", 0) == "a"                # single character word

assert sol.kthCharacter("ab", 0) == "a"               # first block
assert sol.kthCharacter("ab", 1) == "b"               # first occurrence of b
assert sol.kthCharacter("ab", 2) == "b"               # second occurrence of b

assert sol.kthCharacter("abc", 3) == "c"              # start of c block
assert sol.kthCharacter("abc", 5) == "c"              # end of c block

assert sol.kthCharacter("a b", 1) == " "             # space handling
assert sol.kthCharacter("a b", 2) == "b"             # character after space

assert sol.kthCharacter("zzz", 5) == "z"             # repeated same letter

assert sol.kthCharacter("cat dog", 6) == " "         # exact boundary at space

assert sol.kthCharacter("abcd", 9) == "d"            # last position of expansion

Test Summary

Test Why
"hello world", 0 First character of expanded string
"hello world", 15 Position lands on space
"a", 0 Smallest valid input
"ab", 1 Inside repeated block
"ab", 2 End of repeated block
"abc", 3 Beginning of larger block
"abc", 5 End of larger block
"a b", 1 Space handling
"a b", 2 Transition from space to next word
"zzz", 5 Same character repeated many times
"cat dog", 6 Boundary immediately before second word
"abcd", 9 Final valid position

Edge Cases

Single Character Word

A word of length one expands to itself. A common bug is assuming every character has a repeated block larger than one. In this case the only block length is 1. The implementation naturally handles this because the first character receives a block length of position + 1 = 1.

Target Position Falls on a Space

Spaces are preserved exactly once between words. It is easy to focus only on word expansions and accidentally ignore spaces. The implementation explicitly processes spaces as blocks of length one, allowing positions such as the second example to return ' ' correctly.

Target Position at the End of a Large Repetition Block

Suppose the target is the final occurrence of a repeated character, such as the last 'c' in:

abbccc

The condition:

if k < block_length:

correctly identifies any position inside the block, including its last position. This avoids off-by-one errors that often occur when working with ranges of repeated characters.

Very Large Input String

The original string can contain up to 100000 characters. Building the entire expanded string could require substantially more memory. The optimal solution never creates the expansion and instead processes contribution lengths directly, keeping memory usage constant regardless of the expanded size.