# Hash Divided String **Difficulty:** MEDIUM [External](https://leetcode.com/problems/hash-divided-string) Canonical: https://scaleengineer.com/dsa/problems/hash-divided-string **Data structures:** String --- ## 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`. **Example 1:** **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:** **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. # Approaches ## Iterating Through Substrings This approach directly translates the problem description into code. It involves iterating through the string `s` in chunks of size `k`, creating a substring for each chunk, and then processing each substring to calculate the hash character. A `StringBuilder` is used to efficiently build the final result string. **Time:** O(n). The outer loop runs `n/k` times. Inside, creating a substring of length `k` takes O(k) time, and iterating over it also takes O(k) time. Total time is `(n/k) * (O(k) + O(k)) = O(n)`. · **Space:** O(k + n/k). `O(k)` space is required for the temporary `chunk` string in each iteration, and `O(n/k)` space is needed for the `StringBuilder` that stores the result. **Pros:** The code is very readable and closely follows the logic described in the problem statement. **Cons:** Creates `n/k` new substring objects, which leads to unnecessary memory allocation and garbage collection overhead. This can be less performant than direct character access. ### Explanation The algorithm proceeds by dividing the string into `n/k` segments. A loop iterates with a step of `k`, and in each step, `s.substring(i, i + k)` is called to extract the current chunk. While this is conceptually simple, creating a new substring object in each iteration introduces memory and performance overhead. For each extracted substring, we then iterate through its characters to compute the sum of their hash values (`char - 'a'`). The sum is taken modulo 26, converted back to a character, and appended to a `StringBuilder`. This avoids the high cost of repeated string concatenation in Java. ```java class Solution { public String hashDividedString(String s, int k) { StringBuilder result = new StringBuilder(); for (int i = 0; i < s.length(); i += k) { String chunk = s.substring(i, i + k); int currentSum = 0; for (char c : chunk.toCharArray()) { currentSum += c - 'a'; } int hashedValue = currentSum % 26; char hashedChar = (char) ('a' + hashedValue); result.append(hashedChar); } return result.toString(); } } ``` ### Algorithm - Initialize an empty `StringBuilder` called `result`. - Loop from `i = 0` to `s.length() - 1` with a step of `k`. - Inside the loop, create a substring `chunk` from index `i` to `i + k`. - Initialize `currentSum = 0`. - Iterate through each character of the `chunk`. - For each character, add its hash value (`char - 'a'`) to `currentSum`. - After iterating through the chunk, calculate `hashedValue = currentSum % 26`. - Convert `hashedValue` to its corresponding character and append it to `result`. - After the main loop, convert `result` to a string and return it. ## Optimized Single-Pass Iteration This is a more efficient approach that avoids creating intermediate substring objects. It processes the input string `s` in a single pass using a nested loop structure. The outer loop marks the beginning of each `k`-length chunk, and the inner loop iterates through the characters of that chunk using `charAt()` to calculate the sum, thus minimizing memory overhead. **Time:** O(n). The nested loops effectively iterate over each character of the string `s` exactly once. The outer loop runs `n/k` times and the inner loop runs `k` times, for a total of `(n/k) * k = n` constant-time operations. · **Space:** O(n/k). The space required is primarily for the `StringBuilder` to store the output string, which has a length of `n/k`. This is the minimum possible space complexity as it's required for the output itself. **Pros:** Highly efficient as it avoids creating intermediate string objects, reducing memory usage and garbage collection pressure.; Processes the string in a single pass with direct character access, which is generally faster. **Cons:** The nested loop indexing (`j` from `i` to `i+k`) might be considered slightly less intuitive than iterating over a pre-made substring, but it's a standard and efficient pattern. ### Explanation This method optimizes the process by directly accessing characters from the input string `s` instead of creating substrings. We use a `StringBuilder` for efficient result construction. The algorithm employs a nested loop. The outer loop iterates through the string with a step of `k`, defining the start of each chunk. The inner loop then iterates `k` times to cover all characters in the current chunk. Inside the inner loop, `s.charAt(j)` retrieves each character, its hash value is computed and added to a running sum for the chunk. Once the inner loop finishes, the sum is processed (modulo 26) and the resulting character is appended to the `StringBuilder`. This eliminates the overhead of temporary object creation from the substring-based approach. ```java class Solution { public String hashDividedString(String s, int k) { StringBuilder result = new StringBuilder(); int n = s.length(); for (int i = 0; i < n; i += k) { int currentSum = 0; for (int j = i; j < i + k; j++) { currentSum += s.charAt(j) - 'a'; } char hashedChar = (char) ('a' + (currentSum % 26)); result.append(hashedChar); } return result.toString(); } } ``` ### Algorithm - Initialize an empty `StringBuilder` called `result`. - Loop with an outer index `i` from `0` to `s.length() - 1` with a step of `k`. - Inside the outer loop, initialize `currentSum = 0`. - Start an inner loop with index `j` from `i` to `i + k - 1`. - In the inner loop, get the character `s.charAt(j)` and add its hash value (`s.charAt(j) - 'a'`) to `currentSum`. - After the inner loop completes, calculate `hashedValue = currentSum % 26`. - Convert `hashedValue` to its corresponding character and append it to `result`. - After the outer loop, convert `result` to a string and return it. # Solutions ### Java ```java class Solution { public String stringHash(String s, int k) { StringBuilder ans = new StringBuilder(); int n = s.length(); for (int i = 0; i < n; i += k) { int t = 0; for (int j = i; j < i + k; ++j) { t += s.charAt(j) - 'a'; } int hashedChar = t % 26; ans.append((char)('a' + hashedChar)); } return ans.toString(); } } ``` ### CPP ```cpp class Solution { public: string stringHash(string s, int k) { string ans; int n = s.length(); for (int i = 0; i < n; i += k) { int t = 0; for (int j = i; j < i + k; ++j) { t += s[j] - 'a'; } int hashedChar = t % 26; ans += ('a' + hashedChar); } return ans; } }; ``` ### Python ```python 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) ```