Problem

You are given a string s of length n and an integer k, where n is a multiple of k. Your task is to hash the string s into a new string called result, which has a length of n / k.

First, divide s into n / k substrings , each with a length of k. Then, initialize result as an empty string.

For each substring in order from the beginning:

  • The hash value of a character is the index of that character in the English alphabet (e.g., 'a' -> 0, 'b' -> 1, …, 'z' -> 25).
  • Calculate the sum of all the hash values of the characters in the substring.
  • Find the remainder of this sum when divided by 26, which is called hashedChar.
  • Identify the character in the English lowercase alphabet that corresponds to hashedChar.
  • Append that character to the end of result.

Return result.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: s = "abcd", k = 2

Output: "bf"

Explanation:

First substring: `"ab"`, `0 + 1 = 1`, `1 % 26 = 1`, `result[0] = 'b'`.

Second substring: `"cd"`, `2 + 3 = 5`, `5 % 26 = 5`, `result[1] = 'f'`.

Example 2

1
2
3
4
5
6
7
8
9

Input: s = "mxz", k = 3

Output: "i"

Explanation:

The only substring: `"mxz"`, `12 + 23 + 25 = 60`, `60 % 26 = 8`, `result[0] =
'i'`.

Constraints

  • 1 <= k <= 100
  • k <= s.length <= 1000
  • s.length is divisible by k.
  • s consists only of lowercase English letters.

Solution

Method 1 – Simulation by Substring Hashing

Intuition

We divide the string into equal parts, compute the sum of alphabet indices for each part, and map the sum modulo 26 back to a character. This is a direct simulation of the problem statement.

Approach

  1. For each substring of length k, compute the sum of the alphabet indices (where ‘a’ = 0, …, ‘z’ = 25).
  2. Take the sum modulo 26 to get the hashed character index.
  3. Convert the index back to a character and append to the result.
  4. Repeat for all substrings and return the result string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    string hashString(string s, int k) {
        int n = s.size();
        string ans;
        for (int i = 0; i < n; i += k) {
            int sum = 0;
            for (int j = i; j < i + k; ++j) sum += s[j] - 'a';
            ans += (char)('a' + (sum % 26));
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func hashString(s string, k int) string {
    n := len(s)
    ans := make([]byte, 0, n/k)
    for i := 0; i < n; i += k {
        sum := 0
        for j := i; j < i+k; j++ {
            sum += int(s[j] - 'a')
        }
        ans = append(ans, byte('a'+(sum%26)))
    }
    return string(ans)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public String hashString(String s, int k) {
        int n = s.length();
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < n; i += k) {
            int sum = 0;
            for (int j = i; j < i + k; ++j) sum += s.charAt(j) - 'a';
            ans.append((char)('a' + (sum % 26)));
        }
        return ans.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    fun hashString(s: String, k: Int): String {
        val n = s.length
        val ans = StringBuilder()
        for (i in 0 until n step k) {
            var sum = 0
            for (j in i until i + k) sum += s[j] - 'a'
            ans.append(('a'.code + (sum % 26)).toChar())
        }
        return ans.toString()
    }
}
1
2
3
4
5
6
7
8
class Solution:
    def hashString(self, s: str, k: int) -> str:
        n = len(s)
        ans = []
        for i in range(0, n, k):
            total = sum(ord(c) - ord('a') for c in s[i:i+k])
            ans.append(chr(ord('a') + (total % 26)))
        return ''.join(ans)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
struct Solution;
impl Solution {
    pub fn hash_string(s: String, k: i32) -> String {
        let n = s.len();
        let s = s.as_bytes();
        let mut ans = String::new();
        let k = k as usize;
        for i in (0..n).step_by(k) {
            let mut sum = 0;
            for j in i..i+k {
                sum += (s[j] - b'a') as i32;
            }
            ans.push((b'a' + (sum % 26) as u8) as char);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    hashString(s: string, k: number): string {
        let ans = '';
        for (let i = 0; i < s.length; i += k) {
            let sum = 0;
            for (let j = i; j < i + k; ++j) sum += s.charCodeAt(j) - 97;
            ans += String.fromCharCode(97 + (sum % 26));
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of s, since we process each character once.
  • 🧺 Space complexity: O(n/k), for the result string.