# Simple O(n) java solution - easily extend to k characters

• The main idea is to maintain a sliding window with 2 unique characters. The key is to store the last occurrence of each character as the value in the hashmap. This way, whenever the size of the hashmap exceeds 2, we can traverse through the map to find the character with the left most index, and remove 1 character from our map. Since the range of characters is constrained, we should be able to find the left most index in constant time.

``````public class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
if(s.length() < 1) return 0;
HashMap<Character,Integer> index = new HashMap<Character,Integer>();
int lo = 0;
int hi = 0;
int maxLength = 0;
while(hi < s.length()) {
if(index.size() <= 2) {
char c = s.charAt(hi);
index.put(c, hi);
hi++;
}
if(index.size() > 2) {
int leftMost = s.length();
for(int i : index.values()) {
leftMost = Math.min(leftMost,i);
}
char c = s.charAt(leftMost);
index.remove(c);
lo = leftMost+1;
}
maxLength = Math.max(maxLength, hi-lo);
}
return maxLength;
}
}``````

• shouldn't this solution be O(nk) in time complexity?

• k = 2 in this case. So O(kn) = O(2n) = O(n)

• Great solution! I reimplemented it with concise code.

``````public int lengthOfLongestSubstringTwoDistinct(String s) {
Map<Character, Integer> lastSeen = new HashMap<>();
int low = 0, max = 0;
for (int i = 0; i < s.length(); i++) {
lastSeen.put(s.charAt(i), i);
if (lastSeen.size() > 2) {
int toRemoveLastSeen = i;
for (Integer val : lastSeen.values()) toRemoveLastSeen = Math.min(val, toRemoveLastSeen);
lastSeen.remove(s.charAt(toRemoveLastSeen));
low = toRemoveLastSeen + 1;
}
max = Math.max(max, i - low + 1);
}
return max;
}
``````

• This post is deleted!

• Good solution. Use LinkedHashMap for better code.

• Iterating the map every time sounds pretty inefficient and unnecessary. You can keep two variables to save the chars with the leftmost index and rightmost index, so that you can directly access those in O(1) time.

• Two pointer solution avoids all the hashing and will run quicker.

``````    public int LengthOfLongestSubstringTwoDistinct(string s)
{
int left1 = -1;
int left2 = -1;
int len = 0;
int max = 0;
for (int i = 0; i < s.Length; i++)
{
if (left1 == -1 || s[i] == s[left1])
{
left1 = i;
len++;
max = Math.Max(max, len);
}
else if (left2 == -1 || s[i] == s[left2])
{
left2 = i;
len++;
max = Math.Max(max, len);
}
else
{
if (left1 < left2) { len = i - left1; left1 = i; }
else { len = i - left2; left2 = i; }
}
}
return max;
}
``````

• public class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
if(s.length() < 1) return 0;
HashMap<Character,Integer> index = new HashMap<Character,Integer>();
int lo = 0;
int hi = 0;
int maxLength = 0;
while(hi < s.length()) {
if(index.size() <= 2) {
char c = s.charAt(hi);
index.put(c, hi);
hi++;
}
if(index.size() > 2) {
int leftMost = s.length();
for(int i : index.values()) {
leftMost = Math.min(leftMost,i);
}
char c = s.charAt(leftMost);
index.remove(c);
lo = leftMost+1;
}
maxLength = Math.max(maxLength, hi-lo);
}
return maxLength;
}
}

What if Interviewer had asked to return the actual substring rather than just the length?

• This post is deleted!

• @chintan83
I think we could add another variable start to represent the start point of the result. When we update the maxLen, we upate the start at the same time. In the end, we just print s.substring(start, start + maxLen).

``````public int lengthOfLongestSubstringKDistinct(String s, int k) {
if(s == null || s.length() == 0) return 0;
if(s.length() <= k) return s.length();

int left = 0, right = 0;
int maxLen = 0;
int start = 0;
Map<Character, Integer> charIndex = new HashMap<>();
while(right < s.length()){
if(charIndex.size() <= k){
charIndex.put(s.charAt(right), right);
right++;
}
if(charIndex.size() > k){
int leftMost = s.length();
for(int index : charIndex.values()){
leftMost = Math.min(leftMost, index);
}
char c = s.charAt(leftMost);
charIndex.remove(c);
left = leftMost + 1;
}
// maxLen = Math.max(maxLen, right - left);
if(right - left > maxLen){
start = left;
maxLen = right - left;
}
}
System.out.println(s.substring(start, start + maxLen));
return maxLen;
}
``````

Hope it works.

• share my code using array instead of hashmap, beats 70%

``````class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
if (s == null || s.length() == 0)
return 0;
// one corner case is that you walk through the whole string and still no more than 2 distinct
// you have to calculate at last
int beg = 0, end = 0, start = 0, len = Integer.MIN_VALUE, count = 0;
int[] map = new int[128];
while (end < s.length()) { // < or <=?
char c = s.charAt(end);
if (map[c] == 0) // add a new char into temp
count++;
map[c]++;

while (count == 3) { // have 3 distinct chars
// check whether to update len or not
if (end - beg > len) {
len = end - beg;
start = beg;
}
char b = s.charAt(beg);
if (map[b] == 1) // substract one letter and remain 2
count--;
map[b]--;
beg++;
}
end++;
}
// it's possible that you walk to the end without updating the max length
if (count != 3 && end - beg > len) {
len = end - beg;
start = beg;
}
return len==Integer.MIN_VALUE? s.length() : len;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.