Given a list of lowercase alphabet strings words, return the length of the longest contiguous sublist where all words share the same first letter.
Example 1
Input
words = [“she”, “sells”, “seashells”, “he”, “sells”, “clams”]
Output
3
Explanation
[“she”, “sells”, “seashells”] all share the first letter s.
Longest Alliteration Algorithm
The problem is essentially equivalent of finding the longest contiguous numbers in a list. We can do this in quadratic time (O(N^2)) with bruteforce algorithm to check every possible sublist. However, we can do it better with O(N) Linear Algorithm where we need to keep the previous position, and update it when current item is not the same (breaking the sequence).
1 2 3 4 5 6 7 8 9 10 11 12 13 | class Solution: def longestContiguousSequence(self, words): l = len(words) if l == 0: return 0 i, ans, p = 1, 1, 0 while i < l: if words[i][0] != words[p][0]: p = i else: ans = max(ans, i - p + 1) i += 1 return ans |
class Solution:
def longestContiguousSequence(self, words):
l = len(words)
if l == 0:
return 0
i, ans, p = 1, 1, 0
while i < l:
if words[i][0] != words[p][0]:
p = i
else:
ans = max(ans, i - p + 1)
i += 1
return ans–EOF (The Ultimate Computing & Technology Blog)
GD Star Rating
loading...
222 wordsloading...
Last Post: Teaching Kids Programming - Fast and Slow Pointer to Obtain the Middle of the Linked List
Next Post: Teaching Kids Programming - Algorithms to Find the Cycle of a Linked List