Interview Question Longest Substring Without Repeating Characters

By Fatih KABAKCI

The problem is to find length of the longest substring without repeating characters in a given string. In order to solve this problem, each unique, distinct character in each substring is stored in a collection such as Set until same character is already found in the same sequence. After that it is passed into another substring group.

For example when input is abcabcbb,

Problem #3 - Longest Substring Without Repeating Characters

Description: Given a string, find the length of the longest substring without repeating characters.

Difficulty: Medium

Solution in Java

package com.fatihkabakci.Medium.LongestSubStr;

import java.util.HashSet;
import java.util.Set;

/**
 * 
 * @author fkabakci
 * Problem Description: Given a string, find the length of the longest substring without repeating characters.
 * 
 * Examples:
 * 
 * Given "abcabcbb", the answer is "abc", which the length is 3.
 * Given "bbbbb", the answer is "b", with the length of 1.
 * Given "pwwkew", the answer is "wke", with the length of 3. 
 * 
 * Solution:
 * 
 * 1. Get each of character from i to n in the string
 * 2. Check if the set has already that
 * 	  if so, 
 * 			 ignore rest of the other characters in the current group and, 
 *           pass to sub group which is from i + 1 to n in the string.
 * 			 Also remove all data in the set.
 * 	  if not, 
 * 			 add the current character into the set, and 
 * 			 continue with the next character in the same group.
 * 3. Update always length of the longest substring
 * 4. Return length of the longest one
 *
 */
public class LongestSubStringWoRep {
	public static int lengthOfLongestSubstring(String s) {
		if (s.isEmpty() || s.length() == 1)
			return s.length();

		Set<Character> alphaSet = new HashSet<Character>();
		int i = 0, j = 0, maxLength = 1, n = s.length();
		while (j < n) {
			char c = s.charAt(j);
			if (alphaSet.contains(c)) {
				j = i++;
				alphaSet.clear();
			} else {
				alphaSet.add(c);
				j++;
			}
			int currentLength = alphaSet.size();
			if (maxLength < currentLength)
				maxLength = currentLength;
		}
		return maxLength;
	}

	public static void main(String[] args) {

		System.out.println(lengthOfLongestSubstring("abcabcbb"));
		System.out.println(lengthOfLongestSubstring("bbbbb"));
		System.out.println(lengthOfLongestSubstring("pwwkew"));
		System.out.println(lengthOfLongestSubstring("c"));
		System.out.println(lengthOfLongestSubstring(""));
		System.out.println(lengthOfLongestSubstring("au"));
		}
	}

Similar Problems

#5 Longest Palindromic Substring