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

Carvia Tech | May 04, 2019 | 1 min read | 20 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. Top 50 SDET Java Programming Interview Questions & Answers
  2. Write a program to reverse a string using recursion in Java
  3. Write a program to reverse the order of words in a string
  4. Java program to check if two strings are anagrams
  5. Check whether given number is even or odd
  6. How to check if the given number is palindrome in Java
  7. Check if the given number is Armstrong Number in Java



Find more on this topic:
SDET Interviews image
SDET Interviews

End to end automation testing using Selenium Web Driver, Rest Assured, JMeter, Junit, TestNG etc.

Last updated 1 month ago


Recommended books for interview preparation:

This website uses cookies to ensure you get the best experience on our website. more info