Uber | Phone screen | Longest substring with at most K distinct characters

Anonymous User

4466

Q: https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters

I was only able to implement a double for loop brute force solution and got a rejection email 2 hours later. A more optimal solution is obviously preferred.

My solution that works but is not optimal:

import java.util.*;

//Find the longest substring which contains at most M distinct characters
//ababbcbxyz, m = 3, ababbcb (return 7 is the lengh of ababbcb)

public class Solution {
 public static void main(String args[] ) throws Exception {
     System.out.println(longestSubstring("ababbcbxyz", 3)); // 7
     System.out.println(longestSubstring("abcabc", 5)); // 6
     System.out.println(longestSubstring("abababab", 1)); // 1
     System.out.println(longestSubstring("aabbabab", 1)); // 2
     System.out.println(longestSubstring(null, 1)); // 0
 }
 
 private static int longestSubstring(String s, int m) {
     if (s == null || s.length() == 0) {
         return 0;
     }
     
     int maxLength = 1;
     outer: for (int i = 0; i < s.length(); i++) {
         int length = 1;
         int uniqueSeen = 0;
         Set<Character> unique = new HashSet<>(); // space complexity O(n)
         Character c = s.charAt(i);
         unique.add(c);
         for (int j = i + 1; j < s.length(); j++) {
             Character c2 = s.charAt(j);
             if (!unique.contains(c2)) { 
                 unique.add(c2);
                 if (unique.size() > m) {
                     //System.out.println(unique.size());
                     continue outer;
                 }
             }
             length++;
             //System.out.println(c2 + " " + length);
             if (length > maxLength) {
                 maxLength = length;
             }
         }
     }
     return maxLength;
 }
}

Comments (11)