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:
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:
Input: s = "hello world", k = 0
Output: "h"
Explanation:
t = "heelllllllooooo woorrrllllddddd". Therefore, the answer is t[0] = "h".
Example 2:
Input: s = "hello world", k = 15
Output: " "
Explanation:
t = "heelllllllooooo woorrrllllddddd". Therefore, the answer is t[15] = " ".
Constraints:
1 <= s.length <= 105s contains only lowercase English letters and spaces ' '.s does not contain any leading or trailing spaces.s are separated by a single space.0 <= k < t.length. That is, k is a valid index of t.We first split the string s into multiple words by spaces. For each word w, we can calculate the length it occupies in the expanded string t as m=\frac{(1+|w|)cdot |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:
cur = 0 to represent the number of characters that have been expanded so far.w[i] of the word w:cur by i + 1.k < cur, it means the k-th character is 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 s.
Java
C++
Go
TypeScript
Practice Find Kth Character in Expanded String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor