Complexity Estimator | JavaScript

Complexity Optimization for Longest Substring Problem

This document analyzes the time and space complexities of the `lengthOfLongestSubstring` function, highlighting bottlenecks, areas for optimization, and refactoring strategies to achieve linear complexity using efficient data structures

Prompt

function lengthOfLongestSubstring(s: string): number {
    if (s.length === 0) return 0;

    let longestSubString = 0;
    let substringCount = 1;
    let finalCount = 0;
    let substring = s[0];

    for (let i = 0; i < s.length; i++) {
        substring = s[i];
        substringCount = 1;

        for (let j = i + 1; j < s.length; j++) {
            if (!substring.includes(s[j])) {
                substring += s[j];  // Concatenate the character to the substring
                substringCount++;
            } else {
                break;
            }
        }

        if (finalCount < substringCount) {
            finalCount = substringCount;
        }
    }

    return finalCount;
}

Answer

Complexity Analysis of `lengthOfLongestSubstring`

Code Overview

The function lengthOfLongestSubstring finds the length of the longest substring without repeating characters in a given string s.

Time Complexity

Best Case

O(n): This occurs when all characters in the string are unique. The outer loop iterates through each character once, and the inner loop terminates almost instantly for each character.

Average Case

O(n^2): For a typical string with some overlaps in characters, each character will potentially require a linear scan of subsequent characters until a duplicate is found.

Worst Case

O(n^2): In a case where the string consists of repeated characters, each character forces a complete scan of the subsequent characters, which leads to the maximum number of iterations for the inner loop for every outer iteration.

Space Complexity

O(n): The space complexity is determined by the storage required for the longest substring. In the worst situation, where all characters are unique, the program will use space proportional to the size of the input string s to store the substring.

Bottlenecks and Areas for Optimization

Substring Search: The use of substring.includes(s[j]) leads to inefficiency as it checks for the presence of a character in the substring, resulting in O(n) on each inner loop iteration. This leads to a combined O(n^2) complexity.
- Optimization: Use a set to keep track of the characters in the current substring. This improves the character existence check to O(1).
Redundant Outer Loop Iterations: The outer loop could be optimized to skip positions that have been assessed, especially after encountering duplicates.
- Optimization: Use the "two-pointer" technique (or sliding window approach) to maintain the start and end of the current substring dynamically.

Refactored Complexity with Optimizations

Using the suggested optimizations, the overall complexity can be improved to:

Time Complexity: O(n) for both best, average, and worst cases.
Space Complexity: O(min(n, m)), where m is the size of the character set (ASCII characters or Unicode).

Conclusion

The initial implementation exhibits quadratic time complexity due to nested iterations and inefficient substring checks. By refactoring the code with a set and applying the sliding window technique, both time complexity and execution efficiency can be substantially improved. For further learning on such optimization techniques, consider exploring courses on the Enterprise DNA Platform.

Description

This document analyzes the time and space complexities of the lengthOfLongestSubstring function, highlighting bottlenecks, areas for optimization, and refactoring strategies to achieve linear complexity using efficient data structures and algorithms.