Given a String, the task is to write a Python program to compute maximum scoring words i.e words made of characters with a maximum positional summation.
Examples:
Input : test_str = ‘Lazyroar must use neveropen for cs knowledge’
Output : neveropen
Explanation : Sum of characters positional values for “neveropen” word is maximum, hence result.Input : test_str = ‘Lazyroar love neveropen’
Output : neveropen
Explanation : Sum of characters positional values for “neveropen” word is maximum, hence result.
Method #1 : Using split() + loop + ord() + ascii_lowercase
In this, we initially split each word using split(), get positional magnitude using ord(), ascii_lowercase checks for correct pool of characters chosen for evaluation.
Python3
# Python3 code to demonstrate working of # Maximum Scoring word # Using split() + loop + ord() + ascii_lowercase import string # initializing string test_str = 'Lazyroar must use neveropen for cs knowledge' # printing original string print ( "The original string is : " + str (test_str)) score = 0 max_sc = 0 res = '' for wrd in test_str.split(): score = 0 # computing score for lttr in wrd: if lttr in string.ascii_lowercase: score + = ord (lttr) - 96 # updating maximum if score > max_sc: max_sc = score res = wrd # printing result print ( "Maximum scoring word : " + str (res)) |
Output:
The original string is : Lazyroar must use neveropen for cs knowledge Maximum scoring word : neveropen
Method #2 : Using sum() + loop + ord()
Similar to above method, only difference here being sum() is used for task of summation rather than internal loop.
Python3
# Python3 code to demonstrate working of # Maximum Scoring word # Using sum() + loop + ord() import string # initializing string test_str = 'Lazyroar must use neveropen for cs knowledge' # printing original string print ( "The original string is : " + str (test_str)) score = 0 max_sc = 0 res = '' for wrd in test_str.split(): # computing score # sum for cumulation score = sum ( ord (lttr) - 96 for lttr in wrd if lttr in string.ascii_lowercase) # updating maximum if score > max_sc: max_sc = score res = wrd # printing result print ( "Maximum scoring word : " + str (res)) |
Output:
The original string is : Lazyroar must use neveropen for cs knowledge Maximum scoring word : neveropen
Time Complexity: O(n2)
Auxiliary Space: O(n)
Method 3: Using a dictionary to store scores of each word:
Step-by-step approach:
- Split the string into words
- Initialize a dictionary scores to an empty dictionary
- For each word in the list of words:
- Initialize a variable score to 0
- For each character in the word:
- Add the ASCII value of the character to the score
- Add the score as a value to the dictionary with the word as the key
- Return the key with the maximum value in the dictionary
Python3
def max_scoring_word_2(test_str): words = test_str.split() scores = {} for word in words: score = 0 for char in word: score + = ord (char) scores[word] = score return max (scores, key = scores.get) test_str = 'Lazyroar love neveropen' print (max_scoring_word_2(test_str)) # Output: neveropen |
neveropen
Time complexity: O(n*m), where n is the number of words and m is the maximum length of a word
Auxiliary Space: O(n)
Method #3: Using map() + sum() + max()
- Convert the input string into a list of words using the split() method.
- Define a lambda function to calculate the score of each word. This function will use the map() function to map each character to its corresponding score, using ord() – 96, and then calculate the sum of those scores using the sum() function.
- Use the max() function to find the word with the maximum score.
- Print the result.
Python3
import string # initializing string test_str = 'Lazyroar must use neveropen for cs knowledge' # printing original string print ( "The original string is : " + str (test_str)) # define function to calculate score of a word score_func = lambda word: sum ( map ( lambda c: ord (c) - 96 , word)) # split input string into a list of words words = test_str.split() # calculate the score of each word and find the word with maximum score res = max (words, key = score_func) # printing result print ( "Maximum scoring word : " + str (res)) |
The original string is : Lazyroar must use neveropen for cs knowledge Maximum scoring word : neveropen
Time Complexity: O(nk + m).
- The code splits the input string into words using the split() method, which takes O(n) time where n is the length of the string.
- Then it uses the map() function to apply the lambda function to each word, which takes O(k) time where k is the length of the longest word in the string.
- The max() function takes O(m) time, where m is the number of words in the list.
- Therefore, the overall time complexity of this code is O(nk + m).
Auxiliary Space: O(k + m).
- This code uses O(k) extra space to store the lambda function and O(m) extra space to store the list of words.
- The max() function uses O(1) extra space.
- Therefore, the overall auxiliary space complexity of this code is O(k + m).