Given two strings A and B and these strings contain lower case letters. The task is to tell the length of the merged strings. For example, given A is “abcde” and B is “cdefg”, then merging the two strings results in “abcdefg”. The merge operation is performed in such a manner that the joining characters are both the suffix of A and Prefix of B. Before merging you are allowed to do any ONE of the following operations:
- Reverse string A
- Reverse string B
Examples:
Input : A = "ababc" B = "bcabc" Output : Length is 8 the suffix of string A i.e "bc" and prefix of B i.e "bc" is the same so the merged string will be "ababcabc" and length is 8. Input : A = "cdefg" B = "abhgf" Output : Length is 8 the suffix of string A i.e "fg" and prefix of reversed B i.e "fg" is the same so the merged string will be "cdefghba" and length is 8 Input : A = "wxyz" B = "zyxw" Output : Length is 4
Below is the Python code implementation of the above mentioned approach.
Python3
# function to find the length of the# merged stringdef mergedstring(x, y) : k = len(y) for i in range(len(x)) : if x[i:] == y[:k] : break else: k = k-1 # uncomment the below statement to # know what the merged string is # print(a + b[k:]) return len(a + b[k:])# function to find the minimum length# among the merged stringdef merger(a, b): # reverse b b1 = b[::-1] # function call to find the length # of string without reversing string 'B' r1 = mergedstring(a, b) # function call to find the length # of the string by reversing string 'B' r2 = mergedstring(a, b1) # compare between lengths if r1 > r2 : print("Length is", r2) else : print("Length is", r1) # driver codea = "abcbc"b = "bcabc"merger(a, b) |
Output:
Length is 8
Time complexity: O(n^2) where n is the length of the longer string between a and b.
Auxiliary space: O(1) as we are not using any data structures to store intermediate results.
