Longest Substr K Distinct

AlgorithmAlgorithmBeginner
Practice Now

This tutorial is from open-source community. Access the source code

Introduction

This challenge requires finding the length of the longest substring with at most k distinct characters in a given string.


Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL algorithm(("`Algorithm`")) -.-> algorithm/BasicAlgorithmsGroup(["`Basic Algorithms`"]) python(("`Python`")) -.-> python/ControlFlowGroup(["`Control Flow`"]) python(("`Python`")) -.-> python/DataStructuresGroup(["`Data Structures`"]) python(("`Python`")) -.-> python/FunctionsGroup(["`Functions`"]) python(("`Python`")) -.-> python/ModulesandPackagesGroup(["`Modules and Packages`"]) python(("`Python`")) -.-> python/ObjectOrientedProgrammingGroup(["`Object-Oriented Programming`"]) python(("`Python`")) -.-> python/ErrorandExceptionHandlingGroup(["`Error and Exception Handling`"]) algorithm/BasicAlgorithmsGroup -.-> algorithm/arrays_strings("`Arrays Strings`") python/ControlFlowGroup -.-> python/conditional_statements("`Conditional Statements`") python/ControlFlowGroup -.-> python/for_loops("`For Loops`") python/DataStructuresGroup -.-> python/lists("`Lists`") python/DataStructuresGroup -.-> python/tuples("`Tuples`") python/FunctionsGroup -.-> python/function_definition("`Function Definition`") python/ModulesandPackagesGroup -.-> python/standard_libraries("`Common Standard Libraries`") python/ObjectOrientedProgrammingGroup -.-> python/classes_objects("`Classes and Objects`") python/ObjectOrientedProgrammingGroup -.-> python/encapsulation("`Encapsulation`") python/ErrorandExceptionHandlingGroup -.-> python/raising_exceptions("`Raising Exceptions`") python/FunctionsGroup -.-> python/build_in_functions("`Build-in Functions`") subgraph Lab Skills algorithm/arrays_strings -.-> lab-268864{{"`Longest Substr K Distinct`"}} python/conditional_statements -.-> lab-268864{{"`Longest Substr K Distinct`"}} python/for_loops -.-> lab-268864{{"`Longest Substr K Distinct`"}} python/lists -.-> lab-268864{{"`Longest Substr K Distinct`"}} python/tuples -.-> lab-268864{{"`Longest Substr K Distinct`"}} python/function_definition -.-> lab-268864{{"`Longest Substr K Distinct`"}} python/standard_libraries -.-> lab-268864{{"`Longest Substr K Distinct`"}} python/classes_objects -.-> lab-268864{{"`Longest Substr K Distinct`"}} python/encapsulation -.-> lab-268864{{"`Longest Substr K Distinct`"}} python/raising_exceptions -.-> lab-268864{{"`Longest Substr K Distinct`"}} python/build_in_functions -.-> lab-268864{{"`Longest Substr K Distinct`"}} end

Longest Substr K Distinct

Problem

Given a string and an integer k, find the length of the longest substring that contains at most k distinct characters. A substring is a contiguous block of characters. For example, in the string "abcabcdefgghiij", the longest substring with at most 3 distinct characters is "abcabc". If there are multiple substrings with the same length, return any of them.

Requirements

To solve this challenge, the following requirements must be met:

  • The inputs may not be valid, so the code should handle invalid inputs gracefully.
  • The strings are ASCII.
  • The search is case sensitive.
  • A substring is a contiguous block of characters.
  • The result should be an integer.
  • The code should be able to handle the input within memory limits.

Example Usage

The following examples demonstrate the expected behavior of the code:

  • None -> TypeError
  • '', k = 3 -> 0
  • 'abcabcdefgghiij', k=3 -> 6
  • 'abcabcdefgghighij', k=3 -> 7

Summary

The code should handle invalid inputs gracefully, search case sensitively, and return an integer as the result. The code should be able to handle the input within memory limits.

Other Algorithm Tutorials you may like