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
Carvia Tech | 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
- SDET Java Coding Challenges
- Check if the given string is palindrome
- Reverse a string using recursion in Java
- Get distinct words from a given file in Java
- 50 SDET Java Interview Questions & Answers
- Reverse position of words in a string using recursion
Find more on this topic:
Subscribe to Interview Questions
Recommended books for interview preparation:
Book you may be interested in..
Book you may be interested in..
Similar Posts
- Reverse position of words in a string using recursion
- REST Assured with plain/text response body
- Get distinct words from a given file in Java
- SDET Java Coding Challenges
- REST Assured vs Apache HttpClient and RestTemplate
- Java 11 HttpClient with Basic Authentication
- HTTP GET request with Java 11 HttpClient - Kotlin
- HTTP Head request using Java 11 HttpClient - Kotlin
- Using Java 11 HttpClient with Kotlin Coroutines
- Migrating Spring Boot tests from Junit 4 to Junit 5