educative.io

Incorrect solution still passes all test cases

Courses
,
#1

The following solution passes all of the test cases despite being incorrect:

import java.util.*;

class LongestSubstringKDistinct {
  public static int findLength(String str, int k) {
    int longest = 0, windowStart = 0;
    Map<Character, Integer> map = new HashMap<>();
    char[] arr = str.toCharArray();

    for (int windowEnd = 0; windowEnd < arr.length; windowEnd++) {
      char c = arr[windowEnd];
      
      if (!map.containsKey(c) && map.keySet().size() == k) {
        char prev = arr[windowStart];
          while (map.get(prev) > 0) {
            if (arr[windowStart] == prev) {
              map.put(prev, map.get(prev) - 1);
            }

            windowStart++;
          }
          map.remove(prev);
      }

      map.put(c, map.getOrDefault(c, 0) + 1);
      longest = Math.max(longest, (windowEnd - windowStart + 1));
    }

    return longest;
  }
}

Note that the while loop is only checking if a single char is no longer inside the window instead of checking the number of unique chars inside the window.

There should be more robust test cases so that an incorrect solution like the above does not pass.

1 Like
#2

Hi, @Ahmed1

So your code is checking if the size of the key comes equal to k, it will automatically reduce its frequency so there will be no need to check the uniqueness. As for example findLength(araaci, 2) map value on every iteration would be as:

0
{a=1}
1
{a=1, r=1}
2
{a=2, r=1}
3
{a=3, r=1}
4
{r=1, c=1}
5
{r=1, i=1}

Also, you can further use print statements to check what’s happening at each iteration for better understanding. FYI, there is no need to use if (arr[windowStart] == prev) as you are just setting prev equal to arr[windowStart] just above this condition.