Java solution WITHOUT hashmap


  • 7
    G

    The idea is pretty simple. We iterate thru the list once and we keep a pointer of where the current longest possible substring starts. During the iteration, we check if this last character is contained in the current substring. If so, move the ptr to the first index of the char at the string +1. Everytime we will compare and keep the max value up to date.

    I am calling the indexOf() method for strings which can theoretically be O(N). I am guessing this is cheaper than creating a hashmap for this set of test cases? Anyway, I just want to share my alternative solution:

    public class Solution {
        public int lengthOfLongestSubstring(String s) {
            if (s.length() <= 1) return s.length();
            
            int max = 1;
            int ptr = 0;
            for (int i = 1; i< s.length(); i++) {
                // find the first occurence of the char after index ptr
                int index = s.indexOf(s.charAt(i), ptr); 
                if (index < i) { // it means that it is contained in s.substring(ptr, i)
                    ptr = index + 1;
                }
                max = Math.max(max, i - ptr + 1);
            }
            
            return max;
        }
    }

  • 0
    S

    But then the time complexity will go up.


  • 0
    M

    Nice. Overall time complexity will be O(n^2)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.