BAEL-2393: Longest Sub-string without repeating characters.

akash-pandey · akash-pandey · commit 09261fb3b94b · 2018-11-26T23:02:44.000+05:30
diff --git a/algorithms-miscellaneous-1/src/main/java/com/baeldung/algorithms/string/LongestSubstringNonRepeatingCharacters.java b/algorithms-miscellaneous-1/src/main/java/com/baeldung/algorithms/string/LongestSubstringNonRepeatingCharacters.java
@@ -0,0 +1,51 @@
+package com.baeldung.algorithms.string;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+
+public class LongestSubstringNonRepeatingCharacters {
+
+    public static String getNonRepeatingCharactersBruteForce(String input) {
+        String output = "";
+        for (int start = 0; start < input.length(); start++) {
+            Set<Character> visited = new HashSet<>();
+            int end = start;
+            for (; end < input.length(); end++) {
+                char currChar = input.charAt(end);
+                if (visited.contains(currChar)) {
+                    break;
+                } else {
+                    visited.add(currChar);
+                }
+            }
+            if (output.length() < end - start + 1) {
+                output = input.substring(start, end);
+            }
+        }
+        return output;
+    }
+
+    public static String getNonRepeatingCharacters(String input) {
+        Map<Character, Integer> visited = new HashMap<>();
+        String output = "";
+        for (int start = 0, end = 0; end < input.length(); end++) {
+            char currChar = input.charAt(end);
+            if(visited.containsKey(currChar)) {
+                start = Math.max(visited.get(currChar)+1, start);
+            }
+            if(output.length() < end - start + 1) {
+                output = input.substring(start, end+1);
+            }
+            visited.put(currChar, end);
+        }
+        return output;
+    }
+
+    public static void main(String[] args) {
+        String input = "CODINGISAWESOME";
+        System.out.println(getNonRepeatingCharacters(input));
+    }
+
+}
diff --git a/algorithms-miscellaneous-1/src/test/java/com/baeldung/algorithms/string/LongestSubstringNonRepeatingCharactersTest.java b/algorithms-miscellaneous-1/src/test/java/com/baeldung/algorithms/string/LongestSubstringNonRepeatingCharactersTest.java
@@ -0,0 +1,20 @@
+package com.baeldung.algorithms.string;
+
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
+
+public class LongestSubstringNonRepeatingCharactersTest {
+
+    @Test
+    void givenString_whenGetNonRepeatingCharactersBruteForceCalled_thenResultFoundAsExpected() {
+        String input = "CODINGISAWESOME";
+        Assertions.assertEquals("NGISAWE", LongestSubstringNonRepeatingCharacters.getNonRepeatingCharactersBruteForce(input));
+    }
+
+    @Test
+    void givenString_whenGetNonRepeatingCharactersCalled_thenResultFoundAsExpected() {
+        String input = "CODINGISAWESOME";
+        Assertions.assertEquals("NGISAWE",LongestSubstringNonRepeatingCharacters.getNonRepeatingCharacters(input));
+    }
+
+}
