String getNonRepeatingSubstring(String input) {
Map<Character, Integer> visited = new HashMap<>();
String result = "";
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 (result.length() < end - start + 1) {
result = input.substring(start, end + 1);
}
visited.put(currChar, end);
}
return result;
}
Find longest non-repeating substring from a given string in Java
Upasana | May 04, 2019 | 1 min read | 222 views
Approach
-
Traverse the string from position zero till end of length
-
maintain a hashmap of already visited characters
-
Maintain current substring with non-repeating characters with the help of a start and end index.
-
maintain the longest non-repeating substring in
result
variable
Java implementation
NonRepeatingSubstring.java
Unit testing
We can write simple JUNIT based test to assert the correctness of our program.
NonRepeatingStringTest.java
import org.junit.Test;
import static org.hamcrest.CoreMatchers.equalTo;
import static org.junit.Assert.*;
public class NonRepeatingStringTest {
@Test
public void getNonRepeatingSubstring() {
NonRepeatingString utils = new NonRepeatingString();
assertThat(utils.getNonRepeatingSubstring("javaconceptoftheday"), equalTo("oftheday"));
assertThat(utils.getNonRepeatingSubstring("ABDEFGABEF"), equalTo("ABDEFG"));
assertThat(utils.getNonRepeatingSubstring("stackoverflow"), equalTo("stackoverfl"));
}
}
Top articles in this category:
- Find first non-repeating character from a String
- Check if the given string is palindrome
- Reverse a string using recursion in Java
- Get distinct words from a given file in Java
- Java Coding Problems for SDET Automation Engineer
- 50 Java Interview Questions for SDET Automation Engineer
- Reverse position of words in a string using recursion
Recommended books for interview preparation:
Book you may be interested in..
Book you may be interested in..