3271. Hash Divided String

MediumStringSimulation

Problem Description

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.

Intuition

The problem is essentially about converting a string into a new, compressed form by processing it in chunks. This is achieved by dividing the string s into equal-sized substrings and then transforming each substring into a single character through a hashing-like mechanism.

Division into Substrings: Since n is a multiple of k, dividing the string s into substrings of length k is straightforward. This results in n / k substrings.
Hash Calculation: For each of these substrings, compute a hash value by summing up their alphabet index values (e.g., a is 0, b is 1, ...).
Modulo Operation: This sum is then reduced to a single index using modulo 26 (% 26). This ensures that the result is between 0 and 25, perfectly corresponding to an alphabet index.
Character Mapping: Using this reduced index, map it back to a character in the alphabet (e.g., index 0 corresponds to 'a').
Result Construction: The characters derived from all substrings are concatenated to form the final result.

This intuitive approach leverages the properties of modulo operation to ensure that each chunk of the original string contributes a single, predictable character to the result.

Solution Approach

We can simulate this process step-by-step as described in the problem.

Initialization:
- Create an empty list ans to store the characters of the resulting string.
- Iterate over the string s in steps of k to process each substring.
Iterating Over Substrings:
- For each substring defined by a starting index i that increments by k, initialize a sum variable t to keep track of the sum of hash values of characters in the substring.
Calculating Hash Value:
- Iterate over each character position j from i to i + k - 1.
- For each character s[j], compute its hash value as ord(s[j]) - ord('a') and add it to t.
Computing Hashed Character:
- Compute hashedChar as t % 26, which gives the remainder when the sum of hash values (t) is divided by 26.
Mapping to a Character:
- Convert hashedChar back to a character in the English alphabet using chr(ord('a') + hashedChar).
- Append this character to the list ans to build the result progressively.
Constructing the Final Result:
- After processing all substrings, convert the list ans to a string using "".join(ans) and return it as result.

This approach efficiently translates the process described into a clear algorithmic solution, leveraging list operations and character arithmetic.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's go through a small example to illustrate the solution approach.

Suppose we have the string s = "abcdefgh" with length n = 8 and k = 2. According to the problem, n is a multiple of k, so we can divide s into n / k = 4 substrings, each of length k = 2.

Dividing s into Substrings:
- Substring 1: "ab"
- Substring 2: "cd"
- Substring 3: "ef"
- Substring 4: "gh"
Processing Each Substring:
- For "ab":
  - Hash value of 'a': 0
  - Hash value of 'b': 1
  - Sum of hash values: 0 + 1 = 1
  - hashedChar = 1 % 26 = 1
  - Corresponding character: 'b'
- For "cd":
  - Hash value of 'c': 2
  - Hash value of 'd': 3
  - Sum of hash values: 2 + 3 = 5
  - hashedChar = 5 % 26 = 5
  - Corresponding character: 'f'
- For "ef":
  - Hash value of 'e': 4
  - Hash value of 'f': 5
  - Sum of hash values: 4 + 5 = 9
  - hashedChar = 9 % 26 = 9
  - Corresponding character: 'j'
- For "gh":
  - Hash value of 'g': 6
  - Hash value of 'h': 7
  - Sum of hash values: 6 + 7 = 13
  - hashedChar = 13 % 26 = 13
  - Corresponding character: 'n'
Constructing the Final Result:
- The characters 'b', 'f', 'j', and 'n' are concatenated to form the final result: "bfjn".

Thus, the hashed string for s = "abcdefgh" and k = 2 is "bfjn".

Solution Implementation

1class Solution:
2    def stringHash(self, s: str, k: int) -> str:
3        # Initialize a list to store the hashed characters
4        ans = []
5      
6        # Iterate over the string in steps of size 'k'
7        for i in range(0, len(s), k):
8            # Initialize the sum for the current substring block
9            t = 0
10            # Iterate over each character in the current block of size 'k'
11            for j in range(i, min(i + k, len(s))):  # Ensure j is within bounds
12                # Add the character's ordinal value offset by 'a'
13                t += ord(s[j]) - ord('a')
14              
15            # Determine the character from the summed value modulo 26
16            hashed_char = t % 26
17            # Convert it back to a character and add to the result list
18            ans.append(chr(ord('a') + hashed_char))
19      
20        # Join the list into a string and return the result
21        return "".join(ans)
22

1class Solution {
2    public String stringHash(String s, int k) {
3        StringBuilder hashedString = new StringBuilder();
4        int n = s.length();
5
6        // Loop through the string in increments of k
7        for (int i = 0; i < n; i += k) {
8            int sum = 0;
9
10            // Calculate sum of character values in the current block of length k
11            for (int j = i; j < i + k; ++j) {
12                sum += s.charAt(j) - 'a'; // Convert each character to its index ('a' = 0, 'b' = 1, etc.) and add to sum
13            }
14
15            // Calculate the hashed character by taking sum modulo 26
16            int hashedChar = sum % 26;
17          
18            // Append the corresponding character from 'a' to the result
19            hashedString.append((char) ('a' + hashedChar));
20        }
21
22        // Convert StringBuilder to String and return the hashed string
23        return hashedString.toString();
24    }
25}
26

1class Solution {
2public:
3    // Function to compute a simple hash of a given string s using chunks of size k
4    string stringHash(string s, int k) {
5        string ans; // Initialize the result string
6        int n = s.length(); // Get the length of the input string
7      
8        // Loop through the string in increments of k
9        for (int i = 0; i < n; i += k) {
10            int t = 0; // Temporary variable to store sum of character values
11          
12            // Sum up the values of characters in the current chunk of size k
13            for (int j = i; j < i + k && j < n; ++j) {
14                t += s[j] - 'a'; // Convert the character to a number (0 for 'a', 1 for 'b', etc.) 
15            }
16          
17            // Compute the hashed character from the sum modulo 26
18            int hashedChar = t % 26;
19          
20            // Append the hashed character to the answer string
21            ans += ('a' + hashedChar); // Convert back to char and append to the result
22        }
23        return ans; // Return the computed hash
24    }
25};
26

1function stringHash(s: string, k: number): string {
2    // Array to store the resulting hashed characters.
3    const result: string[] = [];
4    // Get the length of the input string.
5    const length: number = s.length;
6
7    // Iterate over the string in chunks of size 'k'.
8    for (let i = 0; i < length; i += k) {
9        let tempSum: number = 0;
10
11        // Sum the character values for the current chunk,
12        // using ASCII value conversions.
13        for (let j = i; j < i + k && j < length; j++) {
14            tempSum += s.charCodeAt(j) - 97;
15        }
16
17        // Calculate the hashed character using modulo operation.
18        const hashedCharCode: number = tempSum % 26;
19        // Convert the hashed character code back to a character and store it.
20        result.push(String.fromCharCode(97 + hashedCharCode));
21    }
22
23    // Join the result array into a single string and return it.
24    return result.join('');
25}
26

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. This is because the code processes each character of the string exactly once in a sequential manner. For each iteration over a segment of length k (which is controlled by the outer loop), there is an inner loop that iterates k times. However, since the total number of operations across all cycles of this pair of loops equals the length of the string n, the overall time complexity remains O(n).

The space complexity is O(1), excluding the space required for the output. This is because the algorithm uses a fixed amount of additional space, irrespective of the input size. Variables such as t and hashedChar require constant space, and the space used by ans depends on the output but is typically not accounted for in complexity analysis focused solely on auxiliary space.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: