Test results - Codility

Tasks Details

medium

1. ConcatenatingOfWords

Concatenate the given words in such a way as to obtain a single word with the longest possible substring composed of one particular letter.

100%

An array of N words is given. Each word consists of small letters ('a' − 'z'). Our goal is to concatenate the words in such a way as to obtain a single word with the longest possible substring composed of one particular letter. Find the length of such a substring.

Write a function:

def solution(words)

that, given an array words containing N strings, returns the length of the longest substring of a word created as described above.

Examples:

1. Given N=3 and words=["aabb", "aaaa", "bbab"], your function should return 6. One of the best concatenations is words[1] + words[0] + words[2] = "aaaaaabbbbab". The longest substring is composed of letter 'a' and its length is 6.

2. Given N=3 and words=["xxbxx", "xbx", "x"], your function should return 4. One of the best concatenations is words[0] + words[2] + words[1] = "xxbxxxxbx". The longest substring is composed of letter 'x' and its length is 4.

3. Given N=4 and words=["dd", "bb", "cc", "dd"], your function should return 4. One of the best concatenations is words[0] + words[3] + words[1] + words[2] = "ddddbbcc". The longest substring is composed of letter 'd' and its length is 4.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

all the words are non−empty and consist only of lowercase letters (a−z);

S denotes the sum of the lengths of words; S is an integer within the range [1..100,000].

Solution

Programming language used Python

Time spent on task 1 minutes

Notes

not defined yet

Code: 09:27:07 UTC, py, autosave

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

#finding array index based on letter
def array_index(a):
    return (ord(a)-97)

def solution(words):
    #initializing two dimmensioned array with results it have 26 elements(amounts of letter in alphabeth)
    #and 4 elements for every letter, where is 1st is maximal prefix lenght, 2nd - amount of elements in 
    #strings that consists of same letter, 3rd - maximal suffix, and 4th is biggest lenght of prefix in 
    #word where is suffix and prefix are exactl same. and middle is longest substring at any place
    results = [[0] * 4 for i in range(26)]
    middle=0
    
    #checking word after word 
    for word in words:
        #if word cosist of one letter then adding 1 to strings that consist of same letter
        if len(word)==1: results[array_index(word)][1] +=1
        #otherwise counting lenght of substrings
        else:
            n=c=count=0
            letter=word[0] #first symbol of word
            #if current symbol is not same
            while (c<len(word)): 
                if letter!=word[c]: 
                    #changing symbols for searching substring
                    letter=word[c]
                    middle=max(middle,count) #checking/saving longest substring
                    if n==0: n=count #saving if it prefix as prefix
                    count=0 #voiding substing symbol counter
                c+=1 #increasing letter number
                count+=1 #increasing substring lenght counter
            m=count #saving suffix when loop is ended
            #adding lenght to result array if string included same symbol.
            if (count==len(word)): results[array_index(word[0])][1] += count
            #otherwise sorting our results
            else:
                #if suffix and prefix strings have different letters, then saving both
                #if theirs values bigger then ones at resulsts array
                if word[0]!=word[-1]:
                    results[array_index(word[0])][0]=max(results[array_index(word[0])][0], n)
                    results[array_index(word[-1])][2]=max(results[array_index(word[-1])][2], m)
                #if suffix and prefix have same letter
                else:
                    i=array_index(word[0])
                    #if prefix is bigger, then trying to save it in resulsts otherwise saving suffix 
                    if (n>m):
                        if (results[i][0] < n): results[i][0] = n        
                        elif (results[i][2] < m): results[i][2] = m
                    #is suffix is bigger then doing it in opposite way
                    elif(m>n):
                        if (results[i][2] < m): results[i][2] = m
                        elif (results[i][0] < n): results[i][0] = n        
                    #if them are equal then saving value at 4th element if it is bigger then previous one
                    #and adding smaller value of 4th element to suffix or prefix
                    else:
                        n, results[i][3] = min(n,results[i][3]), max(n,results[i][3])
                        if (results[i][0]<=results[i][2]) and (results[i][0]<n): results[i][0]=n
                        elif (results[i][2]<results[i][0]) and (results[i][2]<n): results[i][2]=n
                            
    #counting and returning results
    m=0
    for x in results: m=max(m, (sum(x)-min (x[0] ,x[2], x[3]) ) )
    m=max(middle,m) #comparing result also to longest substring
    return(m)

Code: 09:27:18 UTC, py, verify, result: Passed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

#finding array index based on letter
def array_index(a):
    return (ord(a)-97)

def solution(words):
    #initializing two dimmensioned array with results it have 26 elements(amounts of letter in alphabeth)
    #and 4 elements for every letter, where is 1st is maximal prefix lenght, 2nd - amount of elements in 
    #strings that consists of same letter, 3rd - maximal suffix, and 4th is biggest lenght of prefix in 
    #word where is suffix and prefix are exactl same. and middle is longest substring at any place
    results = [[0] * 4 for i in range(26)]
    middle=0
    
    #checking word after word 
    for word in words:
        #if word cosist of one letter then adding 1 to strings that consist of same letter
        if len(word)==1: results[array_index(word)][1] +=1
        #otherwise counting lenght of substrings
        else:
            n=c=count=0
            letter=word[0] #first symbol of word
            #if current symbol is not same
            while (c<len(word)): 
                if letter!=word[c]: 
                    #changing symbols for searching substring
                    letter=word[c]
                    middle=max(middle,count) #checking/saving longest substring
                    if n==0: n=count #saving if it prefix as prefix
                    count=0 #voiding substing symbol counter
                c+=1 #increasing letter number
                count+=1 #increasing substring lenght counter
            m=count #saving suffix when loop is ended
            #adding lenght to result array if string included same symbol.
            if (count==len(word)): results[array_index(word[0])][1] += count
            #otherwise sorting our results
            else:
                #if suffix and prefix strings have different letters, then saving both
                #if theirs values bigger then ones at resulsts array
                if word[0]!=word[-1]:
                    results[array_index(word[0])][0]=max(results[array_index(word[0])][0], n)
                    results[array_index(word[-1])][2]=max(results[array_index(word[-1])][2], m)
                #if suffix and prefix have same letter
                else:
                    i=array_index(word[0])
                    #if prefix is bigger, then trying to save it in resulsts otherwise saving suffix 
                    if (n>m):
                        if (results[i][0] < n): results[i][0] = n        
                        elif (results[i][2] < m): results[i][2] = m
                    #is suffix is bigger then doing it in opposite way
                    elif(m>n):
                        if (results[i][2] < m): results[i][2] = m
                        elif (results[i][0] < n): results[i][0] = n        
                    #if them are equal then saving value at 4th element if it is bigger then previous one
                    #and adding smaller value of 4th element to suffix or prefix
                    else:
                        n, results[i][3] = min(n,results[i][3]), max(n,results[i][3])
                        if (results[i][0]<=results[i][2]) and (results[i][0]<n): results[i][0]=n
                        elif (results[i][2]<results[i][0]) and (results[i][2]<n): results[i][2]=n
                            
    #counting and returning results
    m=0
    for x in results: m=max(m, (sum(x)-min (x[0] ,x[2], x[3]) ) )
    m=max(middle,m) #comparing result also to longest substring
    return(m)

Analysis

▶

example1
First example test.

✔

▶

example2
Second example test.

✔

▶

example3
Third example test.

✔

Code: 09:27:29 UTC, py, verify, result: Passed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

#finding array index based on letter
def array_index(a):
    return (ord(a)-97)

def solution(words):
    #initializing two dimmensioned array with results it have 26 elements(amounts of letter in alphabeth)
    #and 4 elements for every letter, where is 1st is maximal prefix lenght, 2nd - amount of elements in 
    #strings that consists of same letter, 3rd - maximal suffix, and 4th is biggest lenght of prefix in 
    #word where is suffix and prefix are exactl same. and middle is longest substring at any place
    results = [[0] * 4 for i in range(26)]
    middle=0
    
    #checking word after word 
    for word in words:
        #if word cosist of one letter then adding 1 to strings that consist of same letter
        if len(word)==1: results[array_index(word)][1] +=1
        #otherwise counting lenght of substrings
        else:
            n=c=count=0
            letter=word[0] #first symbol of word
            #if current symbol is not same
            while (c<len(word)): 
                if letter!=word[c]: 
                    #changing symbols for searching substring
                    letter=word[c]
                    middle=max(middle,count) #checking/saving longest substring
                    if n==0: n=count #saving if it prefix as prefix
                    count=0 #voiding substing symbol counter
                c+=1 #increasing letter number
                count+=1 #increasing substring lenght counter
            m=count #saving suffix when loop is ended
            #adding lenght to result array if string included same symbol.
            if (count==len(word)): results[array_index(word[0])][1] += count
            #otherwise sorting our results
            else:
                #if suffix and prefix strings have different letters, then saving both
                #if theirs values bigger then ones at resulsts array
                if word[0]!=word[-1]:
                    results[array_index(word[0])][0]=max(results[array_index(word[0])][0], n)
                    results[array_index(word[-1])][2]=max(results[array_index(word[-1])][2], m)
                #if suffix and prefix have same letter
                else:
                    i=array_index(word[0])
                    #if prefix is bigger, then trying to save it in resulsts otherwise saving suffix 
                    if (n>m):
                        if (results[i][0] < n): results[i][0] = n        
                        elif (results[i][2] < m): results[i][2] = m
                    #is suffix is bigger then doing it in opposite way
                    elif(m>n):
                        if (results[i][2] < m): results[i][2] = m
                        elif (results[i][0] < n): results[i][0] = n        
                    #if them are equal then saving value at 4th element if it is bigger then previous one
                    #and adding smaller value of 4th element to suffix or prefix
                    else:
                        n, results[i][3] = min(n,results[i][3]), max(n,results[i][3])
                        if (results[i][0]<=results[i][2]) and (results[i][0]<n): results[i][0]=n
                        elif (results[i][2]<results[i][0]) and (results[i][2]<n): results[i][2]=n
                            
    #counting and returning results
    m=0
    for x in results: m=max(m, (sum(x)-min (x[0] ,x[2], x[3]) ) )
    m=max(middle,m) #comparing result also to longest substring
    return(m)

Analysis

▶

example1
First example test.

✔

▶

example2
Second example test.

✔

▶

example3
Third example test.

✔

Code: 09:27:31 UTC, py, final, score: 100

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

#finding array index based on letter
def array_index(a):
    return (ord(a)-97)

def solution(words):
    #initializing two dimmensioned array with results it have 26 elements(amounts of letter in alphabeth)
    #and 4 elements for every letter, where is 1st is maximal prefix lenght, 2nd - amount of elements in 
    #strings that consists of same letter, 3rd - maximal suffix, and 4th is biggest lenght of prefix in 
    #word where is suffix and prefix are exactl same. and middle is longest substring at any place
    results = [[0] * 4 for i in range(26)]
    middle=0
    
    #checking word after word 
    for word in words:
        #if word cosist of one letter then adding 1 to strings that consist of same letter
        if len(word)==1: results[array_index(word)][1] +=1
        #otherwise counting lenght of substrings
        else:
            n=c=count=0
            letter=word[0] #first symbol of word
            #if current symbol is not same
            while (c<len(word)): 
                if letter!=word[c]: 
                    #changing symbols for searching substring
                    letter=word[c]
                    middle=max(middle,count) #checking/saving longest substring
                    if n==0: n=count #saving if it prefix as prefix
                    count=0 #voiding substing symbol counter
                c+=1 #increasing letter number
                count+=1 #increasing substring lenght counter
            m=count #saving suffix when loop is ended
            #adding lenght to result array if string included same symbol.
            if (count==len(word)): results[array_index(word[0])][1] += count
            #otherwise sorting our results
            else:
                #if suffix and prefix strings have different letters, then saving both
                #if theirs values bigger then ones at resulsts array
                if word[0]!=word[-1]:
                    results[array_index(word[0])][0]=max(results[array_index(word[0])][0], n)
                    results[array_index(word[-1])][2]=max(results[array_index(word[-1])][2], m)
                #if suffix and prefix have same letter
                else:
                    i=array_index(word[0])
                    #if prefix is bigger, then trying to save it in resulsts otherwise saving suffix 
                    if (n>m):
                        if (results[i][0] < n): results[i][0] = n        
                        elif (results[i][2] < m): results[i][2] = m
                    #is suffix is bigger then doing it in opposite way
                    elif(m>n):
                        if (results[i][2] < m): results[i][2] = m
                        elif (results[i][0] < n): results[i][0] = n        
                    #if them are equal then saving value at 4th element if it is bigger then previous one
                    #and adding smaller value of 4th element to suffix or prefix
                    else:
                        n, results[i][3] = min(n,results[i][3]), max(n,results[i][3])
                        if (results[i][0]<=results[i][2]) and (results[i][0]<n): results[i][0]=n
                        elif (results[i][2]<results[i][0]) and (results[i][2]<n): results[i][2]=n
                            
    #counting and returning results
    m=0
    for x in results: m=max(m, (sum(x)-min (x[0] ,x[2], x[3]) ) )
    m=max(middle,m) #comparing result also to longest substring
    return(m)

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(S)

Time complexity parameters:
S - sum of the lengths of words

▶

example1
First example test.

✔

▶

example2
Second example test.

✔

▶

example3
Third example test.

✔

▶

small_simple
N <= 3, S <= 10.

✔

0.036 s

▶

small_random_words
N = 4, S = 20.

✔

▶

small_one_letter_words
N = 5, S = 20, each word consists of one type of letter.

✔

▶

small_words_with_long_substring
N = 4, S = 30, each word contains long substring with one letter.

✔

▶

small_the_longest_prefix_and_suffix_in_one_word
N = 6, S = 50, the longest prefix and the longest suffix occur in the same word.

✔

▶

small_big_answer
N = 8, S = 50, big answer.

✔

▶

medium_random_words
N = 25, S = 400.

✔

▶

medium_one_letter_words
N = 25, S = 200, each word consists of one type of letter.

✔

▶

medium_words_with_long_substring
N = 25, S = 400, each word contains long substring with one letter.

✔

▶

medium_the_longest_prefix_and_suffix_in_one_word
N = 25, S = 400, the longest prefix and the longest suffix occur in the same word.

✔

▶

medium_big_answer
N = 25, S = 400, big answer.

✔

▶

large_random_words
S = 20,000.

✔

▶

large_one_letter_words
S = 20,000, each word consists of one type of letter.

✔

▶

large_words_with_long_substring
S = 20,000, each word contains long substring with one letter.

✔

▶

large_the_longest_prefix_and_suffix_in_one_word
S = 20,000, the longest prefix and the longest suffix occur in the same word.

✔

▶

large_big_answer
S = 20,000, big answer.

✔

▶

max_random_words
S = 100,000.

✔

▶

max_one_letter_words
S = 100,000, each word consists of one type of letter.

✔

▶

max_words_with_long_substring
S = 100,000, each word contains long substring with one letter.

✔

▶

max_the_longest_prefix_and_suffix_in_one_word
S = 100,000, the longest prefix and the longest suffix occur in the same word.

✔

▶

max_big_answer
S = 100,000.

✔