How do I map characters to numbers in Hash Divided String?

Map 'a' to 0, 'b' to 1, ..., 'z' to 25. Sum these for each substring and take modulo 26 to get the hashed character.

Can k be larger than the string length?

No, k must be less than or equal to the string length since each substring has exactly k characters.

What if the string length is not divisible by k?

This problem guarantees the string length is divisible by k, so no remainder handling is needed.

Is there a faster way than summing each substring manually?

Because each character must contribute to the sum, O(n) iteration is required; no asymptotically faster method exists.

Does GhostInterview provide hints for the string plus simulation pattern?

Yes, it guides through substring splitting, character position sums, and modulo mapping specifically for this hashing pattern.

#3271

Medium

auto_awesomestring·结合·模拟

LeetCode 题解工作台

哈希分割字符串

给你一个长度为 n 的字符串 s 和一个整数 k ， n 是 k 的倍数。你的任务是将字符串 s 哈希为一个长度为 n / k 的新字符串 result 。首先，将 s 分割成 n / k 个子字符串，每个子字符串的长度都为 k 。然后，将 result 初始化为一个空字符串。我们依…

字符串模拟

题目描述

给你一个长度为 n 的字符串 s 和一个整数 k ，n 是 k 的倍数。你的任务是将字符串 s 哈希为一个长度为 n / k 的新字符串 result 。

首先，将 s 分割成 n / k 个 子字符串 ，每个子字符串的长度都为 k 。然后，将 result 初始化为一个空字符串。

我们依次从前往后处理每一个 子字符串 ：

一个字符的 哈希值 是它在 字母表 中的下标（也就是 'a' → 0 ，'b' → 1 ，... ，'z' → 25）。
将子字符串中字母的 哈希值 求和。
将和对 26 取余，将结果记为 hashedChar 。
找到小写字母表中 hashedChar 对应的字符。
将该字符添加到 result 的末尾。

返回 result 。

示例 1：

输入：s = "abcd", k = 2

输出："bf"

解释：

第一个字符串为 "ab" ，0 + 1 = 1 ，1 % 26 = 1 ，result[0] = 'b' 。

第二个字符串为： "cd" ，2 + 3 = 5 ，5 % 26 = 5 ，result[1] = 'f' 。

示例 2：

输入：s = "mxz", k = 3

输出："i"

解释：

唯一的子字符串为 "mxz" ，12 + 23 + 25 = 60 ，60 % 26 = 8 ，result[0] = 'i' 。

提示：

1 <= k <= 100
k <= s.length <= 1000
s.length 能被 k 整除。
s 只含有小写英文字母。

lightbulb

解题思路

方法一：模拟

我们可以按照题目描述的步骤模拟即可。

遍历字符串 $s$ ，每次取 $k$ 个字符，计算它们的哈希值之和，记为 $t$ ，然后对 $t$ 取模 $26$ ，找到对应的字符，将其添加到结果字符串的末尾。

最后返回结果字符串即可。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串 $s$ 的长度。忽略答案字符串的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def stringHash(self, s: str, k: int) -> str:
        ans = []
        for i in range(0, len(s), k):
            t = 0
            for j in range(i, i + k):
                t += ord(s[j]) - ord("a")
            hashedChar = t % 26
            ans.append(chr(ord("a") + hashedChar))
        return "".join(ans)

speed

复杂度分析

指标	值
时间	complexity is O(n) because each character is visited once during substring extraction and summing. Space complexity is O(n/k) for the resulting hashed string, plus temporary storage for substring sums.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if you are correctly mapping characters to 0-25 values.
question_mark
Confirm you handle strings of length divisible by k without skipping characters.
question_mark
Ensure your modulo operation maps sums back to lowercase letters correctly.

warning

常见陷阱

外企场景

error
Forgetting to take modulo 26 after summing character positions.
error
Incorrect substring slicing causing index errors or missing characters.
error
Mapping characters incorrectly, e.g., 'a' to 1 instead of 0.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Hash Divided String where k does not divide n, requiring handling remainder characters.
arrow_right_alt
Use uppercase letters and adjust modulo mapping to 26 accordingly.
arrow_right_alt
Instead of sum, use product of character positions modulo 26 for hashing.

help

常见问题

外企场景

继续练习

#3248 矩阵中的蛇 #3324 出现在屏幕上的字符串序列 #3174 清除数字