Katkat
Back

Compute unique-substring length and first unique index

BoeingSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manage character frequency counts and sliding window techniques to identify properties of unique substrings and characters.

Problem Statement

Given a string s, you are required to perform two distinct tasks:

  1. Find the length of the longest substring containing only unique characters.
  2. Find the index of the first character in the string that does not repeat anywhere else in the string. If no such character exists, return -1.

Implement the function analyze_string(s) which returns a tuple containing these two values: (max_unique_length, first_unique_index).

Constraints

  • s consists of English lowercase letters.
  • 0 <= len(s) <= 10^5.

Examples

Example 1: Input: s = "abcabcbb" Output: (3, -1) Explanation: Longest unique substring is "abc" (length 3). All characters 'a', 'b', and 'c' repeat, so there is no unique character.

Example 2: Input: s = "leetcode" Output: (3, 0) Explanation: Longest unique substring is "tco" or "cod" (length 3). The first non-repeating character is 'l' at index 0.

Implementation

def analyze_string(s: str) -> tuple:
    # Return (max_unique_length, first_unique_index)
    pass

Hints

Hint 1

Use a sliding window approach with a set or a dictionary to keep track of characters currently in the window to find the longest substring of unique characters.

Hint 2

For the second part of the problem, use a frequency map (dictionary) to count the occurrences of every character in the string in a single pass.

Hint 3

After computing frequencies, iterate through the string a second time to check which character appears exactly once in the frequency map and return its index.

Follow-up questions

  • How would your approach change if the input string contained Unicode characters rather than just lowercase English letters?
  • Can you find the first non-repeating character in a streaming data scenario where the string is infinite?
  • What is the time and space complexity of your solution, and can you optimize the space if the alphabet size is fixed?