Thursday, June 16, 2016

Most Frequent Substring with length between K and L

There are some conditions, such as string length is between k and l, it contains maximum m unique characters.

Sounds super easy, but I did not pass during the OA. I rewrote it with same algorithms afterward and it passed after correcting a typo. Not feeling easy when facing OA.

I think condition of upper length limit l can be forgotten and lower range k is good enough to work out same result. Because if a longer string is repeated, a shorter one included in it is repeated too..

Here's also an example of using Comparator to change priority queue's sort order to be reversed and based on one of the data element in a combined data structure. same comparator can also be used in a TreeMap directly and then PQ can be forgotten.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
package string;

import java.util.*;

public class MostFrequentSubStringOfLengthKtoM {
 /**
  * 
  * @param k
  *            min length
  * @param l
  *            max length
  * @param m
  *            number of unique characters
  * @param s
  *            the string
  * @return
  */
 static int getCount(int k, int l, int m, String s) {
  Set<Character> uniqueChars = new HashSet<Character>();
  Map<String, Integer> stats = new HashMap<String, Integer>();
  for (int h = 0; h < s.length() - k; h++) {
   for (int t = h + k; t <= s.length() && t <= h + l
     && uniqueChars.size() <= m; t++) {
    uniqueChars.clear();
    String subStr = s.substring(h, t);// this method does not
             // include last position
    if (stats.containsKey(subStr)) {
     stats.put(subStr, stats.get(subStr) + 1);
     populateSet(subStr, uniqueChars);
    } else {
     stats.put(subStr, 1);
    }
   }
  }
  PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<Map.Entry<String, Integer>>(
    stats.size(), new Comparator<Map.Entry<String, Integer>>() {

     @Override
     public int compare(Map.Entry<String, Integer> o1,
       Map.Entry<String, Integer> o2) {
      return o2.getValue() - o1.getValue();
     }

    });
  pq.addAll(stats.entrySet());
  Map.Entry<String, Integer> entry = pq.poll();
  System.out.println(entry.getKey());
  return entry.getValue();
 }

 private static void populateSet(String s, Set<Character> uniqueChars) {
  Objects.requireNonNull(s);
  Objects.requireNonNull(uniqueChars);
  for (char c : s.toCharArray())
   uniqueChars.add(c);

 }

 public static void main(String[] args) {
  System.out.println(getCount(3, 5, 5, " as up up up."));

 }

}

No comments: