Please know the answer for my interviews: A substring is made up of contiguous symbols. Therefore the invariant is a[j] > a[k] for j>k. If the invariant is respected than increase a counter where you maintain the current longest substring observed so far. If the invariant is not respect then reset the counter. Also, when you reset you need to compare the current longest substring observed before the rest with the longest observed in the past. Finally, you may want to maintain the starting point.
Now tell me what is the complexity of this algo?
Linear time.
ReplyDelete