How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at UiPath.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at UiPath during technical interviews.

Compute longest distinct substring, case-insensitive

Company: UiPath

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given a string s, return the length of the longest contiguous substring that contains no repeated characters, treating letters case-insensitively (e.g., 'A' and 'a' are the same). All ASCII symbols and whitespace should be considered valid characters. Provide an algorithm with optimal time complexity, justify its time and space bounds, and discuss edge cases (empty string, all duplicates, Unicode input). For extremely large inputs that cannot fully fit in memory, outline how you would process the stream to compute the answer and the trade-offs involved.

Quick Answer: This question evaluates competency in string processing, character normalization for case-insensitivity, algorithmic complexity analysis, and handling large-scale or streaming inputs.

Given a string s, return the length of the longest contiguous substring that contains no repeated characters when letters are compared case-insensitively. For example, 'A' and 'a' count as the same character. Digits, punctuation, spaces, tabs, newlines, and other ASCII symbols are all valid characters and should be treated normally. Implement an algorithm with optimal time complexity. In an interview discussion, you should also be ready to justify the time and space bounds, explain edge cases such as empty input and all-duplicate strings, discuss why full Unicode case-insensitive handling is trickier than ASCII, and outline how the same sliding-window idea could be adapted for streaming input when the whole string cannot fit in memory. For this coding task, graded tests use ASCII input and require only the returned length.

Constraints

0 <= len(s) <= 200000
Graded test cases use ASCII characters (codes 0-127), including spaces and other whitespace
An O(n) solution is expected

Examples

Input: ("abcABCbb",)

Expected Output: 3

Explanation: Ignoring case, the string behaves like 'abcabcbb'. The longest valid substring has length 3, such as 'abc' or 'bca'.

Input: ("aAbBcC",)

Expected Output: 2

Explanation: Because 'a' conflicts with 'A', 'b' with 'B', and 'c' with 'C', the best you can do is length 2, such as 'Ab' or 'Bc'.

Input: ("A a!@#a",)

Expected Output: 5

Explanation: The longest valid substring is ' a!@#', which has length 5. The final 'a' repeats the earlier 'a' case-insensitively.

Input: ("",)

Expected Output: 0

Explanation: An empty string has no substrings, so the answer is 0.

Input: ("ZZZZ",)

Expected Output: 1

Explanation: All characters are the same letter ignoring case, so any valid substring can only have length 1.

Input: ("a\nA\tb",)

Expected Output: 4

Explanation: Newline and tab are valid characters. The longest valid substring is '\nA\tb', which has length 4.

Solution

def solution(s):
    # Sliding window with last seen position of each normalized character.
    # For ASCII input, lower() is sufficient for case-insensitive comparison.
    # The dictionary holds at most 128 keys on graded tests.
    last_seen = {}
    left = 0
    best = 0

    for right, ch in enumerate(s):
        key = ch.lower()

        if key in last_seen and last_seen[key] >= left:
            left = last_seen[key] + 1

        last_seen[key] = right
        window_len = right - left + 1
        if window_len > best:
            best = window_len

    return best

Time complexity: O(n). Space complexity: O(1) for ASCII inputs (at most 128 distinct normalized characters); O(min(n, charset)) in a generalized character set.

Hints

Use a sliding window: expand the right end one character at a time, and move the left end only when a repeated character appears inside the current window.
Store the most recent index of each normalized character, where normalization makes letters lowercase before comparison.

Quick Overview

This question evaluates competency in string processing, character normalization for case-insensitivity, algorithmic complexity analysis, and handling large-scale or streaming inputs.