[HankerRank] Max Unique Substring Length in a Session

Max Unique Substring Length in a Session

Difficulty: Medium

Given a string of lowercase letters with sessions separated by '' characters, find the maximum length of a substring with all distinct letters within any single session.

Example

Input

sessionString = abcabcbb

Output

3

Explanation

- There is only one session: "abcabcbb". 
- Scanning with a sliding window for distinct letters, the longest substrings without repeats are "abc", "bca" and so on, each of length 3. 
- Therefore, the result is 3.

Input Format

• A single line containing the string sessionString.

Constraints

• 0 <= S.length <= 100000
• For all i in [0, S.length]: S[i] is either '*' or a lowercase letter 'a' to 'z'
• Each session is defined as a maximal contiguous substring of S without '*' characters
• Number of sessions (segments between '*') is at most S.length + 1

Output Format

• A single integer denoting the maximum length among all substrings. If sessionString is empty or contains only '*', output 0.

Sample Input 0

*

Sample Output 0

0

Sample Input 1

aa

Sample Output 1

1 

Consideration:

1. Set function "mySet.count" could check if the coming character was appeared in the substring already.

2. If this character is still unique, add to mySet by mySet.insert function.

3. If this character was appeared in the substring, find the index which had the same character as current end_index points to. Remove those characters before this index from mySet by mySet.erase function. The new start_index will be that index + 1.

4. When there is '*', stop operation -> calculate current max unique substring length -> clear mySet by mySet.clear function -> move to check the substring starting after this '*'.

5. Whenever end_index reaches to the end of the input string, calculate current max unique substring length and return this value.

Code:

/*

 * Complete the 'maxDistinctSubstringLengthInSessions' function below.

 *

 * The function is expected to return an INTEGER.

 * The function accepts STRING sessionString as parameter.

 */

int maxDistinctSubstringLengthInSessions(string sessionString) {

    set<char> mySet;

    int n = sessionString.size();

    //cout << "n = " << n << "\n";

    int start_index=0, end_index=0;

    int maxLength=0, curLength;

    if (n==0) return 0;

    while (1) {

        if (sessionString[end_index]=='*') {

            curLength = end_index - start_index;

            if (curLength>maxLength) {

                maxLength = curLength;

            }

            if ((end_index+1) < n) {

                start_index = end_index + 1;

                end_index = start_index;

            }

            else {

                return maxLength;

            }

            mySet.clear();

        }

        else if (!(mySet.count(sessionString[end_index]))) {

            mySet.insert(sessionString[end_index]);

            if ((end_index+1)<n) {

                end_index++;

            }

            else {

                curLength = mySet.size();

                if (curLength>maxLength) {

                    maxLength = curLength;

                }

                return maxLength;

            }

        }

        else {

            curLength = mySet.size();

            if (curLength>maxLength) {

                maxLength = curLength;

            }

            while (sessionString[start_index]!=sessionString[end_index]) {

                mySet.erase(sessionString[start_index]);

                start_index++;

            }

            start_index++;

            if ((end_index+1) < n) {

                end_index++;

            }      

            else {

                return maxLength;

            }

        }

    }

    return maxLength;

}