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:

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 <= 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}\).

Python3JavaC++GoTypeScript

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]

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 ' ';
    }
}

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 ' ';
    }
};

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 ' '
}

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 ' ';
}

Comments