Repository: TheAlgorithms/Java
Pull request #6007 (2024-10-25 18:21:05)

Add longest substring
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6007?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
All modified and coverable lines are covered by tests :white_check_mark:
> Please [upload](https://docs.codecov.com/docs/codecov-uploader) report for BASE (`master@202879a`). [Learn more](https://docs.codecov.io/docs/error-reference?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#section-missing-base-commit) about missing BASE report.
> Report is 4 commits behind head on master.

<details><summary>Additional details and impacted files</summary>


```diff
@@            Coverage Diff            @@
##             master    #6007   +/-   ##
=========================================
  Coverage          ?   69.05%           
  Complexity        ?     4664           
=========================================
  Files             ?      623           
  Lines             ?    17158           
  Branches          ?     3310           
=========================================
  Hits              ?    11848           
  Misses            ?     4856           
  Partials          ?      454           
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6007?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

Chiefpatwal: Longest Substring Without Repeating Characters

This implementation utilizes the sliding window technique to efficiently find the length of the longest substring without repeating characters. The algorithm maintains a dynamic window that expands and contracts based on character uniqueness, ensuring optimal performance with a time complexity of O(n). This solution enhances our algorithm collection by addressing common string manipulation challenges, providing an essential tool for developers working with text processing.

Patch:
diff --git a/src/main/java/com/thealgorithms/slidingwindow/LongestSubstringWithoutRepeatingCharacters.java b/src/main/java/com/thealgorithms/slidingwindow/LongestSubstringWithoutRepeatingCharacters.java
new file mode 100644
index 00000000..0641730d
--- /dev/null
+++ b/src/main/java/com/thealgorithms/slidingwindow/LongestSubstringWithoutRepeatingCharacters.java
@@ -0,0 +1,46 @@
+package com.thealgorithms.slidingwindow;
+import java.util.HashSet;
+
+/**
+ * The Longest Substring Without Repeating Characters algorithm finds the length of
+ * the longest substring without repeating characters in a given string.
+ *
+ * <p>
+ * Worst-case performance O(n)
+ * Best-case performance O(n)
+ * Average performance O(n)
+ * Worst-case space complexity O(min(n, m)), where n is the length of the string
+ * and m is the size of the character set.
+ *
+ * @author  (https://github.com/Chiefpatwal)
+ */
+public final class LongestSubstringWithoutRepeatingCharacters {
+
+    // Prevent instantiation
+    private LongestSubstringWithoutRepeatingCharacters() {
+    }
+
+    /**
+     * This method finds the length of the longest substring without repeating characters.
+     *
+     * @param s is the input string
+     * @return the length of the longest substring without repeating characters
+     */
+    public static int lengthOfLongestSubstring(String s) {
+        int maxLength = 0;
+        int left = 0;
+        HashSet<Character> charSet = new HashSet<>();
+
+        for (int right = 0; right < s.length(); right++) {
+            // If the character is already in the set, remove characters from the left
+            while (charSet.contains(s.charAt(right))) {
+                charSet.remove(s.charAt(left));
+                left++;
+            }
+            charSet.add(s.charAt(right));
+            maxLength = Math.max(maxLength, right - left + 1);
+        }
+
+        return maxLength;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/slidingwindow/LongestSubstringWithoutRepeatingCharactersTest.java b/src/test/java/com/thealgorithms/slidingwindow/LongestSubstringWithoutRepeatingCharactersTest.java
new file mode 100644
index 00000000..8638a707
--- /dev/null
+++ b/src/test/java/com/thealgorithms/slidingwindow/LongestSubstringWithoutRepeatingCharactersTest.java
@@ -0,0 +1,23 @@
+package com.thealgorithms.slidingwindow;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import org.junit.jupiter.api.Test;
+
+/**
+ * Unit tests for the LongestSubstringWithoutRepeatingCharacters class.
+ *
+ * @author  (https://github.com/Chiefpatwal)
+ */
+public class LongestSubstringWithoutRepeatingCharactersTest {
+
+    @Test
+    public void testLengthOfLongestSubstring() {
+        // Test cases for the lengthOfLongestSubstring method
+        assertEquals(3, LongestSubstringWithoutRepeatingCharacters.lengthOfLongestSubstring("abcabcbb"));
+        assertEquals(1, LongestSubstringWithoutRepeatingCharacters.lengthOfLongestSubstring("bbbbb"));
+        assertEquals(3, LongestSubstringWithoutRepeatingCharacters.lengthOfLongestSubstring("pwwkew"));
+        assertEquals(0, LongestSubstringWithoutRepeatingCharacters.lengthOfLongestSubstring(""));
+        assertEquals(5, LongestSubstringWithoutRepeatingCharacters.lengthOfLongestSubstring("abcde"));
+    }
+}