Galaxy Signal Decoding — Problem Statement & Solution Guide

HashingMediumHashing

TimeO(n)

SpaceO(1) (or O(σ) where σ is the alphabet size)

Problem Description

In a deep-space communication protocol, data packets are encoded as continuous strings of alphanumeric characters. A signal decoder must identify the first contiguous substring of a specified length, k, that contains no repeated characters. This ensures the segment can be processed without collision in the decoding buffer.

Given a string s representing the raw signal and an integer k representing the buffer size, determine the length of the first valid segment. If a substring of length k exists where every character is distinct, return k. If no such substring exists within the entire string, return -1.

Note: The problem asks for the length of the first segment meeting the criteria. Since the segment length is fixed at k, the answer is either k (if found) or -1 (if not found). The core task is to efficiently verify the existence of such a window.

DSA Pattern Breakdown

"Galaxy Signal Decoding"

medium

WHY DOES IT MATTER?

Detecting a collision‑free segment in a stream is a fundamental pattern for buffer management, token parsing, and network protocol design. Mastery of the sliding‑window with hash‑based uniqueness checks equips engineers to solve a wide class of real‑time substring problems efficiently.

OPTIMIZATION CHALLENGE

The key insight is that each character's contribution to the window is monotonic: once a character leaves the window it never needs to be reconsidered for that particular occurrence. By updating a constant‑time frequency map on every move of the pointers, we achieve linear time, eliminating the repeated O(k) scans of the naive method.

REAL-WORLD CONNECTION

Imagine a router's packet buffer that can only hold k bytes without duplication; the router must quickly locate a contiguous block of incoming data that fits without overwriting existing entries. The sliding‑window algorithm mirrors how the router slides over the packet stream, adjusting its start position when a duplicate packet ID is detected.

During an interview, implement the frequency map as an int array of size 128 (or 256) for alphanumerics; it avoids hashmap overhead and makes the code concise. Remember to decrement the count when moving the left pointer, and stop as soon as you hit a count > 1, then shrink the window.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1) (or O(σ) where σ is the alphabet size)

Core Theory — Why This Approach?

The problem is a classic sliding‑window variant of the "longest substring without repeating characters" family. The goal is to locate the first window of size k that contains all unique characters. A naive scan that checks every possible substring of length k would require O(n·k) time because each window needs a full scan for duplicates, which quickly becomes prohibitive for large signals (n up to 10⁵ or more). The optimal paradigm treats the string as a stream and maintains a dynamic window with two pointers (left and right). As the right pointer expands, a frequency map (or fixed‑size array for alphanumerics) records character counts. When a duplicate appears, the left pointer contracts until the window regains uniqueness. Because each character is added and removed at most once, the total work is linear, O(n). This approach leverages the hash‑based constant‑time lookup to enforce the "no‑repeat" invariant efficiently.

Why this works: The sliding window guarantees that at any moment the window size never exceeds k, and the hash map instantly tells us if adding the next character would violate the uniqueness constraint. By moving the left pointer only when necessary, we avoid re‑examining characters, turning what would be a quadratic scan into a single pass. The algorithm thus scales to massive input sizes typical of deep‑space telemetry, where real‑time decoding is essential.

Interview Questions on This Problem

Q1How would you modify the solution if the alphabet size is not limited to ASCII (e.g., Unicode characters) and memory is a concern?

Use a hash map (e.g., unordered_map<char32_t, int>) instead of a fixed‑size array, storing only characters that appear in the current window. This keeps space proportional to the window size (O(k)) rather than the full Unicode range.

Q2Can you adapt the algorithm to return the shortest substring that contains all distinct characters of the entire string?

First compute the set of distinct characters in the whole string, then apply a sliding window that expands until it contains all those characters and contracts to minimize length, yielding O(n) time and O(σ) space where σ is the distinct character count.

Q3What changes are needed if the requirement is to find *all* substrings of length k with unique characters, not just the first one?

Maintain the sliding window as before, but instead of stopping at the first valid window, record each starting index when the window size reaches k and has no duplicates, then continue sliding by moving the left pointer one step and updating the frequency map.

Examples

Example 1

Input

s = "abcde", k = 3

Output

Explanation: The first window of size 3 is "abc". The characters 'a', 'b', and 'c' are all unique. Therefore, a valid segment exists, and the length is 3.

Example 2

Input

s = "aabbc", k = 3

Output

-1

Explanation: Window 1: "aab" contains duplicate 'a's. Window 2: "abb" contains duplicate 'b's. Window 3: "bbc" contains duplicate 'b's. No window of size 3 has all unique characters, so return -1.

Example 3

Input

s = "xyzxyz", k = 3

Output

Explanation: Window 1: "xyz" has unique characters 'x', 'y', 'z'. The condition is met immediately at the first window. Return 3.

Example 4

Input

s = "aabbcc", k = 4

Output

-1

Explanation: Window 1: "aabb" has duplicates. Window 2: "abbc" has duplicate 'b's. Window 3: "bbcc" has duplicates. No valid window of size 4 exists. Return -1.

Constraints

1 <= s.length <= 10^5
1 <= k <= s.length
s consists of lowercase English letters and digits
Time complexity must be O(n) where n is the length of the string

Optimal Approach & Strategy

Use a sliding window with a hash map (or fixed array) to maintain character frequencies, adjusting the window in O(1) per step for overall O(n) time.

Brute Force Approach

Check every possible substring of length k and use a set to test for duplicates, resulting in O(n·k) time.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/);
let idx = 0;
const s = input[idx++];
const k = parseInt(input[idx++], 10);

function findFirstUniqueEndIndex(s, k) {
    const n = s.length;
    if (k > n) return -1;
    for (let i = 0; i + k <= n; i++) {
        const seen = new Set();
        let unique = true;
        for (let j = i; j < i + k; j++) {
            if (seen.has(s[j])) { unique = false; break; }
            seen.add(s[j]);
        }
        if (unique) return i + k; // 1‑based ending index
    }
    return -1;
}

const ans = findFirstUniqueEndIndex(s, k);
console.log(ans);

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

int findFirstUniqueEndIndex(const string &s, int k) {
    int n = s.size();
    if (k > n) return -1;
    for (int i = 0; i + k <= n; ++i) {
        unordered_set<char> seen;
        bool unique = true;
        for (int j = i; j < i + k; ++j) {
            if (seen.count(s[j])) { unique = false; break; }
            seen.insert(s[j]);
        }
        if (unique) return i + k; // 1‑based ending index
    }
    return -1;
}

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

    string s; int k;
    if (!(cin >> s >> k)) return 0;
    int ans = findFirstUniqueEndIndex(s, k);
    cout << ans << "\n";
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    private static int findFirstUniqueEndIndex(String s, int k) {
        int n = s.length();
        if (k > n) return -1;
        for (int i = 0; i + k <= n; i++) {
            Set<Character> seen = new HashSet<>();
            boolean unique = true;
            for (int j = i; j < i + k; j++) {
                char c = s.charAt(j);
                if (!seen.add(c)) { unique = false; break; }
            }
            if (unique) return i + k; // 1‑based ending index
        }
        return -1;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] parts = br.readLine().trim().split("\\s+");
        String s = parts[0];
        int k = Integer.parseInt(parts[1]);
        int ans = findFirstUniqueEndIndex(s, k);
        System.out.println(ans);
    }
}

import sys

def find_first_unique_end_index(s: str, k: int) -> int:
    n = len(s)
    if k > n:
        return -1
    for i in range(0, n - k + 1):
        seen = set()
        unique = True
        for j in range(i, i + k):
            if s[j] in seen:
                unique = False
                break
            seen.add(s[j])
        if unique:
            return i + k  # 1‑based ending index
    return -1

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    s = data[0]
    k = int(data[1])
    ans = find_first_unique_end_index(s, k)
    print(ans)

if __name__ == "__main__":
    main()

const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/);
let idx = 0;
const s = input[idx++];
const k = parseInt(input[idx++], 10);

function findFirstUniqueEndIndex(s, k) {
    const n = s.length;
    if (k > n) return -1;
    for (let i = 0; i + k <= n; i++) {
        const seen = new Set();
        let unique = true;
        for (let j = i; j < i + k; j++) {
            if (seen.has(s[j])) { unique = false; break; }
            seen.add(s[j]);
        }
        if (unique) return i + k; // 1‑based ending index
    }
    return -1;
}

const ans = findFirstUniqueEndIndex(s, k);
console.log(ans);

Asked in Top Tech Interviews

Accenture

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.

Galaxy Signal Decoding Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Hashing

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Galaxy Signal Decoding — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor