Two Pointers For A Linear Solution

Problem today was:

Good morning! Here's your coding interview problem for today.

This problem was asked by Amazon.

Given an integer k and a string s, find the length of the longest substring that contains at most k distinct characters.

For example, given s = "abcba" and k = 2, the longest substring with k distinct characters is "bcb".

The solution I came up with has two pointers: one moves in front, the other one in the back, and you control when each pointer moves depending on what has been added to a hash table. Worst case scenario each pointer will go thru each element of the string once, for a total of O(2N)-time. Here is the code, also on GitHub: https://github.com/marcelodebarros/dailycodingproblem/blob/master/DailyCodingProblem09272018.cs cheers, Marcelo

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;

namespace DailyCodingProblem
{
class DailyCodingProblem09272018
{
public string LongestSubstringDistinctK(string str, int k)
{
if (String.IsNullOrEmpty(str)) return str;

Hashtable htChars = new Hashtable();
int back = 0;
int front = back;
int beginSolution = 0;
int endSolution = 0;

while (front < str.Length)
{
if ( (htChars.Count < k && !htChars.ContainsKey(str[front])) ||
(htChars.Count <= k && htChars.ContainsKey(str[front])) )
{
if (front - back > endSolution - beginSolution)
{
beginSolution = back;
endSolution = front;
}
if (!htChars.ContainsKey(str[front]))
{
htChars.Add(str[front], 1);
}
else
{
htChars[str[front]] = (int)htChars[str[front]] + 1;
}
front++;
}
else
{
//Remove the back and move it
htChars[str[back]] = (int)htChars[str[back]] - 1;
if ((int)htChars[str[back]] == 0) htChars.Remove(str[back]);
back++;
}
}

return str.Substring(beginSolution, endSolution - beginSolution + 1);
}
}
}