Find longest non-repeating substring from a given string in Java

Carvia Tech | May 04, 2019 | 1 min read | 11 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

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;
}

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"));
    }
}