- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Suppose we have a list of lowercase alphabetical strings called words, we have to find the maximum sum of the lengths of two distinct words that do not share a common letter. So, if the input is like words = ["abcd", "mno", "abdcmno", "amno"], then the output will be 7, as the words do not share any common letters are ["abcd", "mno"], total length is 7.

To solve this, we will follow these steps −

- Define a function sign() . This will take word
- value := 0
- for each c in word, do
- value := value OR (2^(ASCII of c - ASCII of 'a'))

- return value
- From the main method, do the following
- signature := a list with sign(x) for each x in words
- ans := 0
- for i in range 0 to size of words, do
- for j in range i + 1 to size of words, do
- if signature[i] AND signature[j] is same as 0, then
- ans := maximum of ans and size of words[i] + size of words[j]

- if signature[i] AND signature[j] is same as 0, then

- for j in range i + 1 to size of words, do
- return ans

Let us see the following implementation to get better understanding −

class Solution: def sign(self, word): value = 0 for c in word: value = value | (1 << (ord(c) - 97)) return value def solve(self, words): signature = [self.sign(x) for x in words] ans = 0 for i in range(len(words)): for j in range(i + 1, len(words)): if signature[i] & signature[j] == 0: ans = max(ans, len(words[i]) + len(words[j])) return ans ob = Solution() words = ["abcd", "mno", "abdcmno", "amno"] print(ob.solve(words))

["abcd", "mno", "abdcmno", "amno"]

7

- Related Questions & Answers
- Program to find maximum number of non-overlapping substrings in Python
- Program to find maximum sum of two non-overlapping sublists in Python
- Maximum length product of unique words in JavaScript
- Program to find maximum length of subarray with positive product in Python
- Python - Find words greater than given length
- Program to find maximum sum of non-adjacent nodes of a tree in Python
- Program to find maximum non negative product in a matrix in Python
- Find maximum length Snake sequence in Python
- Python program to print even length words in a string
- Program to find maximum number of non-overlapping subarrays with sum equals target using Python
- Program to find length of shortest supersequence in Python
- Program to find minimum length of lossy Run-Length Encoding in Python
- Program to get maximum length merge of two given strings in Python
- Program to find length of longest balanced subsequence in Python
- Program to find length of longest anagram subsequence in Python

Advertisements