Find substrings

https://app.codesignal.com/interview-practice/task/Ki9zRh5bfRhH6oBau/description

You have two arrays of strings, words and parts. Return an array that contains the strings from words, modified so that any occurrences of the substrings from parts are surrounded by square brackets [], following these guidelines:

If several parts substrings occur in one string in words, choose the longest one. If there is still more than one such part, then choose the one that appears first in the string.

Example

For words = ["Apple", "Melon", "Orange", "Watermelon"] and parts = ["a", "mel", "lon", "el", "An"], the output should be
findSubstrings(words, parts) = ["Apple", "Me[lon]", "Or[a]nge", "Water[mel]on"].

While "Watermelon" contains three substrings from the parts array, "a", "mel", and "lon", "mel" is the longest substring that appears first in the string.

Input/Output

• [execution time limit] 3 seconds (java)

• [input] array.string words

  An array of strings consisting only of uppercase and lowercase English letters.

  Guaranteed constraints:
  0 ≤ words.length ≤ 104,
  1 ≤ words[i].length ≤ 30.

• [input] array.string parts

  An array of strings consisting only of uppercase and lower English letters. Each string is no more than 5 characters in length.

  Guaranteed constraints:
  0 ≤ parts.length ≤ 105,
  1 ≤ parts[i].length ≤ 5,
  parts[i] ≠ parts[j].

• [output] array.string

--

	String[] findSubstrings(String[] words, String[] parts) {
	String[] ans = new String[words.length];
	Set<String> all = new HashSet<String>();
	TreeSet<Integer> lengths = new TreeSet<Integer>((a, b) -> b - a);
	for (String p: parts) {
	all.add(p);
	lengths.add(p.length());
	}
	Map<Integer, List<String>> map = new HashMap<Integer, List<String>>();
	for (int w = 0; w < words.length; w++) {
	map.put(w, new ArrayList<String>());
	for (int l: lengths) {
	for (int i = 0; i + l <= words[w].length(); i++) {
	String sub = words[w].substring(i, i + l);
	map.get(w).add(sub);
	}
	}
	}
	int out = 0;
	for (int w = 0; w < words.length; w++) {
	boolean found = false;
	for (int i = 0; i < map.get(w).size() && !found; i++) {
	String sub = map.get(w).get(i);
	if (all.contains(sub)) {
	StringBuilder sb = new StringBuilder();
	int index = words[w].indexOf(sub);
	sb.append(words[w].substring(0, index));
	sb.append("[");
	sb.append(sub);
	sb.append("]");
	sb.append(words[w].substring(index + sub.length()));
	ans[out++] = sb.toString();
	found = true;
	}
	}
	if (!found) {
	ans[out++] = words[w];
	}
	}
	return ans;
	}

view raw FindSubstrings.java hosted with ❤ by GitHub