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

Carvia Tech | May 04, 2019 | 1 min read | 222 views


Approach

  1. Traverse the string from position zero till end of length

  2. maintain a hashmap of already visited characters

  3. Maintain current substring with non-repeating characters with the help of a start and end index.

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

Top articles in this category:
  1. Find first non-repeating character from a String
  2. SDET Java Coding Challenges
  3. Check if the given string is palindrome
  4. Reverse a string using recursion in Java
  5. Get distinct words from a given file in Java
  6. 50 SDET Java Interview Questions & Answers
  7. Reverse position of words in a string using recursion

Find more on this topic:

Recommended books for interview preparation: