Shift Hash Characters — Problem Statement & Solution Guide

StringsEasySlow/Fast Pointers

TimeO(n)

SpaceO(n)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Strings and solve the Shift Hash Characters problem optimally.

TopicStrings

PatternSlow/Fast Pointers

TimeO(n)

SpaceO(n)

Problem Description

You are provided with a string s consisting of lowercase English letters and the hash symbol #. The goal is to transform the string by relocating every occurrence of # to the end of the string. During this process, the relative order of all non-hash characters must remain strictly preserved. Return the resulting string after all hash symbols have been shifted to the tail.

This operation can be viewed as a stable partitioning of the string where the partition key is the character #. Non-hash elements maintain their original sequence, while hash elements are appended in the order they were encountered (though since they are identical, their relative order is trivially preserved).

DSA Pattern Breakdown

"Shift Hash Characters"

easy

WHY DOES IT MATTER?

Stable partitioning appears in many real‑world data pipelines where you need to filter or segregate records without disturbing their chronological order, such as moving error logs to a separate file while keeping normal logs in sequence.

OPTIMIZATION CHALLENGE

The key insight is to avoid repeated deletions or shifts by counting the special characters in a single pass and constructing the result in one go, turning a quadratic operation into linear time.

REAL-WORLD CONNECTION

Think of a production line where defective items (marked by '#') are diverted to a side conveyor at the end of the line; the good items continue forward in the same order, mirroring how we shift hashes to the tail while preserving the rest.

During an interview, write the linear‑scan solution first, then mention the in‑place variant for languages with mutable arrays; this shows both algorithmic clarity and practical optimization awareness.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

The problem is a classic instance of stable partitioning, where we need to reorder elements of a sequence based on a predicate (character == '#') while preserving the relative order of the elements that do not satisfy the predicate. A naive solution would repeatedly scan the string, remove each hash, and append it to the end, leading to O(n²) time because each removal shifts the remaining characters. The optimal paradigm leverages a two‑pointer or counting technique that processes the string in a single linear pass, accumulating non‑hash characters in order and counting hashes to be appended later. This approach is rooted in the concept of in‑place stable rearrangement, which is widely used in array manipulation, streaming algorithms, and memory‑constrained environments.

In practice, we treat the string as an immutable sequence (as in most high‑level languages) and construct a new result string. We iterate once, appending every non‑hash character to a builder and incrementing a counter for each '#'. After the pass, we concatenate the builder with a string of '#' repeated counter times. The algorithm runs in O(n) time and O(n) auxiliary space for the builder, which is optimal because any solution must examine each character at least once. This linear‑time stable partition is also the foundation for problems like moving zeroes to the end of an array or segregating vowels from consonants.

Interview Questions on This Problem

Q1How would you modify the solution if the input string could contain uppercase letters and you needed to move all non‑alphabetic symbols (including '#') to the end while preserving case‑sensitive order?

Use the same linear scan, but change the predicate to !Character.isLetter(ch). Append letters (preserving case) to the builder, count non‑letters, and finally append the counted symbols. The time and space complexities remain O(n) and O(n) respectively.

Q2Can you solve the problem in O(1) extra space if the language allows mutable strings or character arrays?

Yes. Convert the string to a char array, use two indices: one read pointer scanning from left to right and one write pointer tracking the next position for a non‑hash character. When a non‑hash is encountered, swap it with the element at the write pointer and increment the write pointer. After the scan, fill the remaining positions with '#'. This in‑place algorithm runs in O(n) time and O(1) extra space.

Q3Why is the stable order of non‑hash characters important, and how would the solution differ if stability were not required?

Stability ensures the output respects the original relative ordering, which may be a functional requirement (e.g., preserving user‑entered text). Without stability, we could simply count hashes and then place all non‑hash characters in any order, possibly using a bucket sort or partition algorithm that swaps elements arbitrarily, which could reduce constant factors but would change the output semantics.

Examples

Example 1

Input

s = "ab#cd#ef"

Output

"abcdef##"

Explanation: 1. Identify non-hash characters: 'a', 'b', 'c', 'd', 'e', 'f'. 2. Identify hash characters: '#', '#'. 3. Preserve the relative order of non-hash characters: "abcdef". 4. Append all hash characters to the end: "##". 5. Concatenate the results: "abcdef##".

Example 2

Input

s = "#a#b#c"

Output

"abc###"

Explanation: 1. Identify non-hash characters: 'a', 'b', 'c'. 2. Identify hash characters: '#', '#', '#'. 3. Preserve the relative order of non-hash characters: "abc". 4. Append all hash characters to the end: "###". 5. Concatenate the results: "abc###".

Example 3

Input

s = "xyz"

Output

"xyz"

Explanation: 1. Identify non-hash characters: 'x', 'y', 'z'. 2. Identify hash characters: None. 3. Preserve the relative order of non-hash characters: "xyz". 4. Append all hash characters to the end: "" (empty string). 5. Concatenate the results: "xyz".

Example 4

Input

s = "###"

Output

"###"

Explanation: 1. Identify non-hash characters: None. 2. Identify hash characters: '#', '#', '#'. 3. Preserve the relative order of non-hash characters: "" (empty string). 4. Append all hash characters to the end: "###". 5. Concatenate the results: "###".

Constraints

1 <= s.length <= 10^5
s consists of lowercase English letters and the character '#'.

Optimal Approach & Strategy

Perform a single pass, collect non‑hash characters, count hashes, then concatenate the collected string with the appropriate number of '#', achieving O(n) time.

Brute Force Approach

Repeatedly find a '#' in the string, remove it, and concatenate it to the end; each removal shifts the remaining characters, leading to O(n²) time.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim();

let hashCount = 0;
let result = '';
for (const ch of input) {
    if (ch === '#') {
        hashCount++;
    } else {
        result += ch;
    }
}
result += '#'.repeat(hashCount);
console.log(result);

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    if (!(cin >> s)) return 0;

    string result;
    int hashCount = 0;
    for (char c : s) {
        if (c == '#') {
            ++hashCount;
        } else {
            result.push_back(c);
        }
    }
    result.append(hashCount, '#');
    cout << result << '\n';
    return 0;
}

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int hashCount = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '#') {
                hashCount++;
            } else {
                sb.append(c);
            }
        }
        for (int i = 0; i < hashCount; i++) {
            sb.append('#');
        }
        System.out.println(sb.toString());
    }
}

import sys

def main():
    s = sys.stdin.readline().strip()
    hash_count = s.count('#')
    result = ''.join(ch for ch in s if ch != '#') + '#' * hash_count
    print(result)

if __name__ == "__main__":
    main()

const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim();

let hashCount = 0;
let result = '';
for (const ch of input) {
    if (ch === '#') {
        hashCount++;
    } else {
        result += ch;
    }
}
result += '#'.repeat(hashCount);
console.log(result);

Asked in Top Tech Interviews

Zomato

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.