3744. Find Kth Character in Expanded String 🔒

中文文档

Description

You are given a string s consisting of one or more words separated by single spaces. Each word in s consists of lowercase English letters.

We obtain the expanded string t from s as follows:

• For each word in s, repeat its first character once, then its second character twice, and so on.

For example, if s = "hello world", then t = "heelllllllooooo woorrrllllddddd".

You are also given an integer k, representing a valid index of the string t.

Return the kth character of the string t.

 

Example 1:

Example 2:

 

Constraints:

• 1 <= s.length <= 105
• s contains only lowercase English letters and spaces ' '.
• s does not contain any leading or trailing spaces.
• All the words in s are separated by a single space.
• 0 <= k < t.length. That is, k is a valid index of t.

Solutions

Solution 1: Math + Simulation

We first split the string $\textit{s}$ into multiple words by spaces. For each word $\textit{w}$, we can calculate the length it occupies in the expanded string $\textit{t}$ as $m=\frac{(1+|\textit{w}|)\cdot |\textit{w}|}{2}$.

If $k = m$, it means the $k$-th character is a space, and we can directly return a space.

If $k > m$, it means the $k$-th character is not in the expanded part of the current word. We subtract the expanded length $m$ of the current word and the space length $1$from$k$, and continue processing the next word.

Otherwise, the $k$-th character is in the expanded part of the current word. We can find the $k$-th character by simulating the expansion process:

• Initialize a variable $\textit{cur} = 0$ to represent the number of characters that have been expanded so far.
• Iterate through each character $\textit{w}[i]$ of the word $\textit{w}$:
  • Increase $\textit{cur}$ by $i + 1$.
  • If $k < \textit{cur}$, it means the $k$-th character is $\textit{w}[i]$, and we return this character.

The time complexity is $O(n)$ and the space complexity is $O(n)$, where $n$ is the length of the string $\textit{s}$.

Python3

class Solution:
    def kthCharacter(self, s: str, k: int) -> str:
        for w in s.split():
            m = (1 + len(w)) * len(w) // 2
            if k == m:
                return " "
            if k > m:
                k -= m + 1
            else:
                cur = 0
                for i in range(len(w)):
                    cur += i + 1
                    if k < cur:
                        return w[i]

Java

class Solution {
    public char kthCharacter(String s, long k) {
        for (String w : s.split(" ")) {
            long m = (1L + w.length()) * w.length() / 2;
            if (k == m) {
                return ' ';
            }
            if (k > m) {
                k -= m + 1;
            } else {
                long cur = 0;
                for (int i = 0;; ++i) {
                    cur += i + 1;
                    if (k < cur) {
                        return w.charAt(i);
                    }
                }
            }
        }
        return ' ';
    }
}

C++

class Solution {
public:
    char kthCharacter(string s, long long k) {
        stringstream ss(s);
        string w;
        while (ss >> w) {
            long long m = (1 + (long long) w.size()) * (long long) w.size() / 2;
            if (k == m) {
                return ' ';
            }
            if (k > m) {
                k -= m + 1;
            } else {
                long long cur = 0;
                for (int i = 0;; ++i) {
                    cur += i + 1;
                    if (k < cur) {
                        return w[i];
                    }
                }
            }
        }
        return ' ';
    }
};

Go

func kthCharacter(s string, k int64) byte {
	for _, w := range strings.Split(s, " ") {
		m := (1 + int64(len(w))) * int64(len(w)) / 2
		if k == m {
			return ' '
		}
		if k > m {
			k -= m + 1
		} else {
			var cur int64
			for i := 0; ; i++ {
				cur += int64(i + 1)
				if k < cur {
					return w[i]
				}
			}
		}
	}
	return ' '
}

TypeScript

function kthCharacter(s: string, k: number): string {
    for (const w of s.split(' ')) {
        const m = ((1 + w.length) * w.length) / 2;
        if (k === m) {
            return ' ';
        }
        if (k > m) {
            k -= m + 1;
        } else {
            let cur = 0;
            for (let i = 0; ; ++i) {
                cur += i + 1;
                if (k < cur) {
                    return w[i];
                }
            }
        }
    }
    return ' ';
}