Shift Hash Characters ā Problem Statement & Solution Guide
Problem Description
You are given a string s. Rearrange the characters of s such that all hash characters ('#') are moved to the end of the string, while the relative order of all other characters remains unchanged. Return the modified string.
Examples
Input
abc#
Output
abc##
Explanation: Step-by-step: with input 'abc#', we first initialize two pointers, one at the beginning of the string and one at the end. We then iterate through the string, moving non-hash characters to the front and hash characters to the end. In this case, we move 'a', 'b', and 'c' to the front, and '#' to the end, resulting in the output 'abc##'.
Input
code#
Output
code##
Explanation: Step-by-step: with input 'code#', we first initialize two pointers, one at the beginning of the string and one at the end. We then iterate through the string, moving non-hash characters to the front and hash characters to the end. In this case, we move 'c', 'o', 'd', and 'e' to the front, and '#' to the end, resulting in the output 'code##'.
Constraints
- 1 <= s.length <= 10^5
- s consists only of lowercase English letters and '#' characters.
Optimal Approach & Strategy
Convert the string to a mutable array and use a two-pointer read/write approach. The write pointer tracks the placement of non-hash characters, which are copied forward sequentially, and the rest of the array is backfilled with hashes in a single pass.
Brute Force Approach
Iterate through the string, and whenever we find a hash character, shift all subsequent characters one position to the left and place the hash at the end of the string. This requires shifting elements repeatedly, leading to an O(nĀ²) time complexity.
Verified Code Solutions
function shiftHashCharacters(s) { let nonHash = []; let hash = []; for (let char of s) { if (char === '#') { hash.push(char); } else { nonHash.push(char); } } return nonHash.join('') + hash.join(''); }class Solution {
public String shiftHashCharacters(String s) {
StringBuilder nonHashChars = new StringBuilder();
StringBuilder hashChars = new StringBuilder();
for (char c : s.toCharArray()) {
if (c != '#') {
nonHashChars.append(c);
} else {
hashChars.append(c);
}
}
return nonHashChars.toString() + hashChars.toString();
}
}def shift_hash_characters(s: str) -> str:
non_hash_chars = [char for char in s if char != '#']
hash_chars = [char for char in s if char == '#']
return ''.join(non_hash_chars + hash_chars)function shiftHashCharacters(s) { let nonHash = []; let hash = []; for (let char of s) { if (char === '#') { hash.push(char); } else { nonHash.push(char); } } return nonHash.join('') + hash.join(''); }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.