10.19 Max Unique Substring Length in a Session

10.19.1 Problem Metadata

10.19.2 Description

Given a string of lowercase letters with sessions separated by '*' characters, find the maximum length of a substring with all distinct letters within any single session.

10.19.3 Examples

Example 1:

Input: sessionString = "abcabcbb"
Output: 3
Explanation: There is only one session: "abcabcbb". Scanning with a sliding window for distinct letters, the longest substrings without repeats are "abc", "bca" and so on, each of length 3. Therefore, the result is 3.

Example 2:

Input: sessionString = "*"
Output: 0
Explanation: The string contains only '*', so there are no valid sessions.

Example 3:

Input: sessionString = "aa"
Output: 1
Explanation: There is only one session: "aa". The longest substring with distinct letters is "a" with length 1.

10.19.4 Constraints

  • 0 <= sessionString.length <= 100000
  • For all characters in sessionString: each character is either '*' or a lowercase letter 'a' to 'z'
  • Each session is defined as a maximal contiguous substring without '*' characters
  • Number of sessions (segments between '*') is at most sessionString.length + 1
  • If sessionString is empty or contains only '*', output 0

10.19.5 Solution - Split Sessions and Sliding Window

10.19.5.1 Walkthrough

This solution uses a two-level approach that combines string splitting with the sliding window technique from Longest Substring Without Repeating Characters:

  1. Split by sessions: Use split("\\*") to separate the input into individual sessions
  2. Apply sliding window per session: For each non-empty session, apply the standard sliding window algorithm to find the longest substring with unique characters
  3. Track global maximum: Maintain the maximum length across all sessions

Key insight: This problem is essentially applying LeetCode #3 (Longest Substring Without Repeating Characters) to multiple independent substrings created by splitting on '*'.

Example walkthrough with s = "abc*de*fgh":

Step 1: Split by '*'
  Input: "abc*de*fgh"
  Sessions: ["abc", "de", "fgh"]

Step 2: Process each session with sliding window
  Session "abc":
    - All characters unique
    - Max length: 3

  Session "de":
    - All characters unique
    - Max length: 2

  Session "fgh":
    - All characters unique
    - Max length: 3

Step 3: Return global maximum
  result = max(3, 2, 3) = 3

Example walkthrough with s = "a*bc*aabbc":

Step 1: Split by '*'
  Input: "a*bc*aabbc"
  Sessions: ["a", "bc", "aabbc"]

Step 2: Process each session
  Session "a":
    - Max length: 1

  Session "bc":
    - Max length: 2

  Session "aabbc":
    - Sliding window finds "ab", "abc", "bc" as unique substrings
    - Max length: 3 (from "abc")

Step 3: Return global maximum
  result = max(1, 2, 3) = 3

Edge cases handled: - Empty string: split() returns empty array, result remains 0 - Only asterisks "***": All sessions are empty strings, skipped by !str.isEmpty() - No asterisks "abcabc": Single session processed normally - Leading/trailing asterisks "*abc*": Creates empty sessions that are filtered out

10.19.5.2 Analysis

  • Time Complexity: O(n) where n is the total length of the input string
    • Splitting by '*': O(n) to scan the entire string
    • Processing all sessions: Each character is visited at most twice (once by right pointer, once by left pointer in sliding window)
    • Total: O(n) + O(n) = O(n)
  • Space Complexity: O(n)
    • split() creates an array of session strings: O(n) in worst case when there are no '*' characters
    • HashSet<Character> seen: O(min(m, 26)) where m is the length of the longest session (at most 26 lowercase letters)
    • Dominant factor: O(n) for the split result array

10.19.5.3 Implementation Steps

  1. Split input string: Use split("\\*") to separate sessions (note the escaped asterisk for regex)
  2. Initialize result tracker: Set result = 0 to track the maximum length across all sessions
  3. Process each session:
    • Check if session is non-empty using !str.isEmpty()
    • Call helper function lengthOfLongestSubstring(str) to find max unique substring length
    • Update result with the maximum of current result and session result
  4. Return result: The maximum length found across all sessions
  5. Helper function lengthOfLongestSubstring: Implements the standard sliding window algorithm:
    • Initialize HashSet to track characters in current window
    • Use two pointers: left pointer at index 0, right pointer expanding through the string
    • Expand window by moving right pointer: Add each character to the set
    • When duplicate found: Shrink window from left pointer until duplicate is removed
    • Track maximum window size using right - left + 1

10.19.5.4 Code - Java

class Result {

    /*
     * Complete the 'maxDistinctSubstringLengthInSessions' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts STRING sessionString as parameter.
     */

    public static int maxDistinctSubstringLengthInSessions(String sessionString) {
        String[] splitStrings  = sessionString.split("\\*");
        int result = 0;
        
        for(String str: splitStrings) {
            if(!str.isEmpty()) {
                result = Math.max(result, lengthOfLongestSubstring(str));
            }
        }

        return result;
    }
    
    private static int lengthOfLongestSubstring(String s) {
        Set<Character> seen = new HashSet<>();
        int l = 0;
        int longest = 0;

        for (int r = 0; r < s.length(); r++) {
            char c = s.charAt(r);
            while (seen.contains(c)) {
                seen.remove(s.charAt(l));
                l++;
            }
            seen.add(c);
            longest = Math.max(longest, r - l + 1);
        }

        return longest;
    }

}