Added task 30.

javadev · javadev · commit 83bbea4780e0 · 2021-08-01T17:52:32.000+03:00
diff --git a/src/main/java/s0019.remove.nth.node.from.end.of.list/ListNode.java b/src/main/java/s0019.remove.nth.node.from.end.of.list/ListNode.java
@@ -14,4 +14,14 @@ public class ListNode {
         this.val = val;
         this.next = next;
     }
+
+    public String toString() {
+        String result = "";
+        ListNode nextCopy = next;
+        while (nextCopy.next != null) {
+            result += ", " + nextCopy.val;
+            nextCopy = nextCopy.next;
+        }
+        return result;
+    }
 }
diff --git a/src/main/java/s0030.substring.with.concatenation.of.all.words/Solution.java b/src/main/java/s0030.substring.with.concatenation.of.all.words/Solution.java
@@ -0,0 +1,51 @@
+package s0030.substring.with.concatenation.of.all.words;
+
+import java.util.*;
+
+public class Solution {
+    public List<Integer> findSubstring(String s, String[] words) {
+        List<Integer> output = new ArrayList<>();
+        if (s == null || words == null || s.length() == 0 || words.length == 0) {
+            return output;
+        }
+        int wordLen = words[0].length(), wordsCount = 0;
+        Map<String, Integer> wordToCount = new HashMap<>();
+        for (String word : words) {
+            wordToCount.put(word, wordToCount.getOrDefault(word, 0) + 1);
+            wordsCount++;
+        }
+        int substringLen = wordLen * wordsCount;
+        for (int start = 0; start < wordLen; start++) {
+            Queue<String> queue = new LinkedList<>();
+            Map<String, Integer> substrWordToCount = new HashMap<>();
+            for (int lo = start, hi = start; hi <= s.length() - wordLen; hi += wordLen) {
+                String word = s.substring(hi, hi + wordLen);
+                if (!wordToCount.containsKey(word)) {
+                    queue = new LinkedList<>();
+                    lo = hi + wordLen;
+                    substrWordToCount = new HashMap<>();
+                } else {
+                    int substrWordCount = substrWordToCount.getOrDefault(word, 0);
+                    if (substrWordCount >= wordToCount.get(word)) {
+                        while (!queue.peek().equals(word)) {
+                            String wordToRemove = queue.poll();
+                            int count = substrWordToCount.get(wordToRemove);
+                            if (count == 1) substrWordToCount.remove(wordToRemove);
+                            else substrWordToCount.put(wordToRemove, count - 1);
+                            lo += wordLen;
+                        }
+                        lo += wordLen;
+                        queue.poll();
+                    } else {
+                        substrWordToCount.put(word, substrWordCount + 1);
+                    }
+                    queue.offer(word);
+                    if (queue.size() == wordsCount) {
+                        output.add(lo);
+                    }
+                }
+            }
+        }
+        return output;
+    }
+}
diff --git a/src/test/java/s0019.remove.nth.node.from.end.of.list/SolutionTest.java b/src/test/java/s0019.remove.nth.node.from.end.of.list/SolutionTest.java
@@ -9,19 +9,21 @@ public class SolutionTest {
     @Test
     public void fourSum() {
         ListNode head = new ListNode();
-        head.val = 1;
         ListNode node1 = new ListNode();
-        node1.val = 2;
+        node1.val = 1;
         head.next = node1;
         ListNode node2 = new ListNode();
-        node2.val = 3;
+        node2.val = 2;
         node1.next = node2;
         ListNode node3 = new ListNode();
-        node3.val = 4;
+        node3.val = 3;
         node2.next = node3;
         ListNode node4 = new ListNode();
-        node4.val = 5;
+        node4.val = 4;
         node3.next = node4;
-        assertThat(new Solution().removeNthFromEnd(head, 2).toString(), equalTo("[1, 2, 3, 5]"));
+        ListNode node5 = new ListNode();
+        node5.val = 5;
+        node4.next = node5;
+        assertThat(new Solution().removeNthFromEnd(head, 2).toString(), equalTo("1, 2, 3, 5"));
     }
 }
diff --git a/src/test/java/s0030.substring.with.concatenation.of.all.words/SolutionTest.java b/src/test/java/s0030.substring.with.concatenation.of.all.words/SolutionTest.java
@@ -0,0 +1,17 @@
+package s0030.substring.with.concatenation.of.all.words;
+
+import static org.hamcrest.CoreMatchers.equalTo;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import org.junit.Test;
+
+public class SolutionTest {
+    @Test
+    public void findSubstring() {
+        assertThat(
+                new Solution()
+                        .findSubstring("barfoothefoobarman", new String[] {"foo", "bar"})
+                        .toString(),
+                equalTo("[0, 9]"));
+    }
+}
