educative.io

Running time of Longest Substring with K Distinct Characters

Courses
,
#1

From the explanation of the solution for the Longest Substring with K Distinct Characters the below is stated.

The outer for loop runs for all characters, and the inner while loop processes each character only once; therefore, the time complexity of the algorithm will be O(N+N)

This refers to these loops.

 for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
  ...
  while ((int)charFrequencyMap.size() > k) {
   ...
    }
   
  }
}

My question is if we have a nested loop can it still give linear running time?

#2

Hi @Jamal_Moore,

You can assume here that the inner while loop is just an if statement, which runs only once.
I hope that simplifies things :slight_smile:

Kind Regards,
Khizar Shabir
Developer Advocate

#3

@Khizar_Shabir thanks for the feedback.

I saw that in the explanation but was not quite sure. I will try to wrap my head around it more.

Jamal

1 Like