Skip to content

340 Find the longest substring with k unique characters in a given string

"aabbcc", k = 1
Max substring can be any one from {"aa" , "bb" , "cc"}.

"aabbcc", k = 2
Max substring can be any one from {"aabb" , "bbcc"}.

"aabbcc", k = 3
There are substrings with exactly 3 unique characters
{"aabbcc" , "abbcc" , "aabbc" , "abbc" }
Max is "aabbcc" with length 6.

"aaabbb", k = 3
There are only two unique characters, thus show error message.

::: 💡

  • Sliding window
  • Dictionary for char count :::

C# Solution

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

namespace Algorithms.Medium
{
  public class LongestSubstringWithKUniqueChar
  {
    public static int Get(string vs, int target)
    {

      var l = 0;
      var ans = new List<string>();
      var max = 0;
      var uniqChars = new Dictionary<char, int>(); // total

      if (target == 0) return max;

      foreach (var r in Enumerable.Range(0, vs.Length))
      {
        uniqChars[vs[r]] = uniqChars.ContainsKey(vs[r]) ? uniqChars[vs[r]] + 1 : 1;

        while (uniqChars.Count > target)
        {
          var tempChar = vs[l];

          if (uniqChars[tempChar] == 1)
          {
            uniqChars.Remove(tempChar);

          }
          else
          {
            uniqChars[tempChar] = uniqChars[tempChar] - 1;
          }
          l++;
        }
        max = Math.Max(max, r - l + 1);
      }

      return max;
    }
  }
}

C# Tests

using System.Collections.Generic;
using Algorithms.Medium;
using Xunit;

namespace AlgorithmTests.Medium
{
  public class LongestSubstringWithKUniqueCharTests
  {
    [Fact]
    public void TestName()
    {
      Assert.Equal(6, LongestSubstringWithKUniqueChar.Get("aabbcc", 3));
    }

    [Fact]
    public void TestName1()
    {
      Assert.Equal(4, LongestSubstringWithKUniqueChar.Get("aabbcc", 2));
    }

    [Fact]
    public void TestName2()
    {
      Assert.Equal(2, LongestSubstringWithKUniqueChar.Get("aabbcc", 1));
    }

    [Fact]
    public void TestName3()
    {
      Assert.Equal(3, LongestSubstringWithKUniqueChar.Get("eceba", 2));
    }
  }
}

Geeksforgeeks Solutions

Company

  • Microsoft 03/15/2021