MGM-finduniqsubstrings.py

# Task Description

# Given a string, how many different substrings exist in it that have no repeating characters? Two substrings are considered different if they have a different start or end index.

 

# Example

# s = "abac"

 

# The substrings that have no repeating characters in them are "a", "b", "a", "c", "ab", "ba", "ac", and "bac". Note that "aba" and "abac" do not qualify because the character 'a' is repeated in them. Also note that two substrings, "a" and "a", both qualify because their start indices are different: s[0] and s[2]. There are 8 substrings that have no repeating characters.

 
# Function Description

# Complete the function findSubstrings in the editor below.

 

# findSubstrings has the following parameter:

    # string s:  the given string

# Returns

    # int: the number of substrings in s that have no repeating characters

 

# Constraints

# 1 ≤ length of s ≤ 105

# s consists of only lowercase English letters, ascii['a'-'z'].

 

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'findSubstrings' function below.
#
# The function is expected to return an INTEGER.
# The function accepts STRING s as parameter.
#

def findSubstrings(s):
    # Time complexity : O(N)
    count = 0
    
    l = len(s)
    uniqueStrs = []
    alphaCount = [0]*26
    
    i, j= 0,0
    
    while(i<l):           
        if (j < l and alphaCount[ord(s[j]) - ord('a')] == 0):
            alphaCount[ord(s[j]) - ord('a')] += 1
            count += (j - i + 1)
            j+=1    
            uniqueStrs.append(s[i:j])
        else:
            alphaCount[ord(s[i]) - ord('a')] -= 1
            i+=1
            
    return count



if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    s = input()

    result = findSubstrings(s)

    fptr.write(str(result) + '\n')

    fptr.close()