Longest substring without repeating characters

Question

I have the following O(N) code submitted:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int currentLongest = 0, idx = 0;

        if (s.length() <= 1){ return s.length(); }

        for (int i=1; i<s.length(); i++){
            String str = s.substring(idx, i);  //substring up to current char (exclusive)
            int strLen = str.length();
            int idxOf = str.indexOf(s.charAt(i));  //check if current char is in the substring

            if (idxOf != -1){  //if contains duplicate
                if (strLen > currentLongest){
                    currentLongest = strLen;  //replace if it is the longest substring seen
                }
                idx += idxOf+1; //move front pointer after idxOf.
            }

            if (i == s.length() -1){  // if last iteration, do final check inclusive of last char
                strLen = s.substring(idx, i+1).length();
                if (strLen > currentLongest){
                    currentLongest = strLen;
                }
            }
        }
        return currentLongest;
    }
}

which passes all the test cases, however, I feel its kind of a hodge podge mix of hacks and work arounds (ie the s.length() < 1 part). Not only that, I m unsure if the substring() and indexOf() calls are causing the performance to be worse as follows.

Runtime: 11 ms, faster than 71.13% of Java online submissions for Longest Substring Without Repeating Characters.

Memory Usage: 49.2 MB, less than 19.11% of Java online submissions for Longest Substring Without Repeating Characters.

Requirements:

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Example 2:

Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. Example 3:

Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Answer 1

Thinking about time complexity

Yes the solution runs in \$O(n)\$ time, but only because of the finite size of the alphabet.

With a simple twist, changing the task from a string of characters to an array of numbers, to find the longest sub-array without repeating numbers, the algorithm would run in \$O(n^2)\$ time.

I thought it's worth noting, and something to think about.

Avoid unnecessary computations

The String::substring method creates a new string from the range of characters. This has the cost of allocating memory and copying the range of characters.

It's good to avoid creating substrings when it can be avoided, especially in a loop.

For example in the loop it's wasteful to create an increasingly long substring in every iteration. You could instead work with indexes and the indexOf and lastIndexOf methods.

Although this is only executed once, I want to call it out:

strLen = s.substring(idx, i+1).length();

Better use simple math:

strLen = i + 1 - idx;

Avoid special treatments

This can be avoided:

if (s.length() <= 1){ return s.length(); }

It takes a simple change in the initialization steps:

int currentLongest = 0, idx = 0;

for (int i=0; i<s.length(); i++){

The special treatment for the last character can also be avoided, by updating currentLongest always, not only when finding duplicates.

if (idxOf != -1) {
    if (strLen > currentLongest){
        currentLongest = strLen;
    }
    idx += idxOf+1;
} else {
    strLen = i + 1 - idx;
    if (strLen > currentLongest) {
        currentLongest = strLen;
    }
}

Btw, do you see what I'm seeing? A conditional is duplicated in both branches of an if-else, and it can be safely moved out:

if (idxOf != -1) {
    idx += idxOf+1;
} else {
    strLen = i + 1 - idx;
}

if (strLen > currentLongest) {
    currentLongest = strLen;
}

Note that this simplification opportunity was less visible before. By making just one thing simpler, many times it leads to another thing that can be simpler, then another, and so on.

Initialize variables inside the loop statement if they are not needed outside

Instead of this:

int currentLongest = 0, idx = 0;

for (int i=0; i<s.length(); i++){

This is better:

int currentLongest = 0;

for (int i=0, idx = 0; i<s.length(); i++){

Because idx is only used inside the loop. If it's declared in the loop statement, that makes it impossible to use it outside by mistake.

Use simpler natural names

Some of the variable names are a bit complex or cryptic, for example:

• In currentLongest the term "current" is redundant, because there are no "other kind of longest" in the code. So it could be simply longest.
• idx, is basically the start index of a sequence of unique characters. So it could be start or left.
• strLen is a cryptic name. It contains a length, so it could be simply length.
• idxOf... of what? It's the last index of the current char, so it could be lastIndex.

Alternative implementation

Eliminating the unnecessary string copies, and applying other ideas from above:

int longest = 0;

for (int i = 0, left = 0; i < s.length(); i++) {
    int lastIndex = s.lastIndexOf(s.charAt(i), i - 1);

    if (lastIndex >= left) {
        left = lastIndex + 1;
    } else {
        int length = i + 1 - left;
        longest = Math.max(longest, length);
    }

}
return longest;        

Answer 2

Not really linear

The worst case behavior of indexOf is itself linear in the size of the string. As a result, we have a loop that iterates \$n\$ times that calls a method that is itself \$\mathcal{O}(n)\$. Overall, that's \$\mathcal{O}(n^2)\$.

One could argue that the size of the alphabet is constant. In Java, a char is a sixteen-bit integer and 2¹⁶ is a constant (65,536). However, that same argument could be used with string length. In Java, a String is at most 2³¹ characters long. So we could say that your algorithm is \$\mathcal{O}(1)\$. A rather large constant, but constant.

By convention, when doing this kind of analysis, we normally pretend that the input string could be of infinite length. Even though the implementation limits the actual length. Similarly, I would argue that it's best to treat the alphabet as if it could also be of infinite size.

We usually describe this case as \$\mathcal{O}(nm)\$, where \$n\$ is the length of the input string and \$m\$ is the output. It's worth noting that the worst case is when the output is the length of the input string, i.e. \$n = m\$. Then the algorithm is \$\mathcal{O}(n^2)\$ in the worst case.

Could be linear

It's possible to make a linear time algorithm. To do that, we need to convert the indexOf operation to something constant time. We can do that by saving the most recent location of a character in a data structure with constant time access, e.g. a HashMap or array.

Consider the following variant of the @janos alternative:

final int ALPHABET_SIZE = 65536;

int longest = 0;
int[] lastIndexes = new int[ALPHABET_SIZE];
Arrays.fill(lastIndexes, -1);

for (int right = 0, left = 0, length = s.length(); right < length; right++) {
    int c = (int)s.charAt(right);

    if (lastIndexes[c] >= left) {
        left = lastIndexes[c] + 1;
    } else {
        longest = Math.max(longest, 1 + right - left);
    }

    lastIndexes[c] = right;
}

return longest;

Now, indexOf is a constant time operation: lastIndexes[c]. This makes the algorithm linear in time at the expense of increasing the memory footprint.

Linear may not be faster

From a theoretical standpoint, a linear algorithm will always beat a quadratic algorithm given a large enough input. But in practice, the "large enough input" may be larger than what the implementation can process. Therefore, in practice, a quadratic algorithm may be faster than a loglinear algorithm. For example, many system sorts use an insertion sort (quadratic) for small numbers of elements. Even though they use a divide-and-conquer approach (e.g. mergesort, heapsort, or quicksort) with larger numbers of elements.

This is especially an issue here, as while \$m\$ is \$\mathcal{O}(n)\$ in the worst case, the typical case is going to be better. And most of the time, we don't have to check the full \$m\$ places on a particular iteration. So the expected case is often better than the worst case.

In this case, it is possible that the lastIndexOf solution might only look in cache while the linear variant has to go to memory. That is even likely if we are talking about normal input. So before you get too far into this, remember Knuth's advice to avoid optimization until you know you need it. And if you do think you need it, profile to make sure that your alternative is better.

Answer 3

// How do you find the length of the longest substring non repeating characters?

let str1 = "abcabcbb";
longestSubstring(str1)
function longestSubstring(str) {
    debugger
    let nonRepeating = "";
    let repeating = ""
    for (let i = 0; i <str.length; i++) {
        debugger
        if (!nonRepeating.includes(str[i])) {
            nonRepeating += (str[i]);
        }        
        else{
            repeating+= (str[i])
        }
    }
    console.log(` ${nonRepeating} longest substring non repeating characters length ${nonRepeating.length}`)
    console.log(` ${repeating} longest substring repeating characters length ${repeating.length}`)
}