Longest Distinct Characters in the String

In this class, We discuss the Longest Distinct Characters in the String.

The reader can take a complete competitive coding course. Click Here.

The reader should have basic coding skills to understand competitive coding.

Take the placement training course for basic coding skills. Click Here.

Question:

Given a string S.

Find the longest distinct character set in the String.

Example:

Input: Learningmonkey

Output: 7

gmonkey is the longest distinct character set possible in learningmonkey.

Time complexity: O(|S|)

Space complexity: O(1)

Logic:

Use an array of size 256 to maintain the count of occurrence of the character.

We use the sliding window model to solve this example.

We provide a step-by-step explanation in the video.

Code:

class Solution:

    def longestdistinctchar(self, S):

        maxlength=0

        if(len(S)==0):

            return 0

        elif(len(S) ==1):

            return 1

        visited=[False]*256

        left=right=0

        for c in range(len(S)):

            if((visited[ord(S[c])])==False):

                visited[ord(S[c])]=True

            else:

                maxlength = max(maxlength, (right – left))

                while(left<right):

                    if(S[left]!=S[right]):

                        visited[ord(S[left])]=False

                    else:

                        left+=1

                        break

                    left+=1

            right+=1

        maxlength = max(maxlength, (right – left))

        return maxlength

s=input()

ob = Solution()

z=ob.longestdistinctchar(s)

print(z)