Given a string list, the task is to write a Python program to extract Strings that form the longest increasing alphabetic order at the Kth index. K should be less than the minimum length of all strings.
Input : test_list = [“gfg”, “is”, “best”, “for”, “neveropen”, “and”, “cs”], K = 0
Output : [‘best’, ‘for’, ‘neveropen’]
Explanation : Longest subsequence extracted by comparing 0th index. At 0th index, b < f < g. Longest possible consecution. Next being ‘a’ becomes smaller than ‘g’, hence streak breaks.Input : test_list = [“gfg”, “is”, “neveropen”, “and”, “cs”], K = 0
Output : [‘gfg’, ‘is’]
Explanation : Longest subsequence extracted by comparing 0th index.Input : test_list = [“gfg”, “is”, “neveropen”, “and”, “cs”], K = 4
Output : []
Explanation : Smallest lengths in string, is 2 of ‘is’ and ‘cs’. Since K >= min_length, No result.
Method: Using loop with sliding window
In this, we keep checking for increasing the longest substrings using the sliding window technique and keep updating the maximum of substrings sequence and updating the result list.
At last, the result is printed accordingly.
Example:
Python3
# Python3 code to demonstrate working of# Longest Alphabetic order of Kth index# Using loop with sliding window# initializing listtest_list = ["gfg", "is", "best", "for", "neveropen", "and", "cs"]# printing original listprint("The original list is : " + str(test_list))# initializing KK = 1res = []curr = test_list[:1]for idx in range(1, len(test_list)): # checking for greater element if test_list[idx][K] <= test_list[idx - 1][K]: # comparing current with maximum length if len(curr) > len(res): res = curr curr = [test_list[idx]] else: curr.append(test_list[idx])if len(curr) > len(res): res = curr# printing resultprint("Longest increasing Alphabetic order : " + str(res)) |
The original list is : ['gfg', 'is', 'best', 'for', 'neveropen', 'and', 'cs'] Longest increasing Alphabetic order : ['neveropen', 'and', 'cs']
Time Complexity: O(n), where n is the length of the given list.
Auxiliary Space: O(n)
Approach#2: list + max()
The code creates sublists of consecutive elements from the input list whose k-th index is in alphabetical order. It then returns the longest sublist.
Algorithm
1. Initialize an empty list to store all the increasing sublists.
2. Iterate through the given list.
3. If the current element is greater than the previous element, then append the current element to the sublist.
4. If the current element is smaller than or equal to the previous element, then start a new sublist with the current element.
5. Iterate through the sublist list and return the longest sublist.
Python3
def longest_alphabetic_order(list_, k): sublists = [] current_sublist = [] for i in range(len(list_)): if i == 0 or list_[i][k] >= list_[i-1][k]: current_sublist.append(list_[i]) else: sublists.append(current_sublist) current_sublist = [list_[i]] sublists.append(current_sublist) longest_sublist = max(sublists, key=len) return longest_sublistlist_ = ["gfg", "is", "best", "for", "neveropen", "and", "cs"]k=1print(longest_alphabetic_order(list_, k)) |
['neveropen', 'and', 'cs']
Time complexity: O(nlogn) due to the use of max function.
Auxiliary Space: O(n).
Method 3 : Using dynamic programming.
step-by-step approach:
- Create a list of length n (the length of input list_), filled with 1’s. This list will represent the length of the longest increasing sublist ending at each index.
- For each index i in the range 1 to n-1 (inclusive), compare the value at index i with the value at index i-1. If the value at index i is greater than or equal to the value at index i-1, set the value at index i in the list created in step 1 to be 1 plus the value at index i-1 in that list.
- After step 2 is complete, find the index j with the maximum value in the list created in step 1. This index represents the end of the longest increasing sublist.
- Traverse the list in reverse order, starting from index j, and add each element to the beginning of a result list, as long as its value in the list created in step 1 is one less than the value of the previous element added to the result list. Stop when the value of the current element in the list created in step 1 is not one less than the value of the previous element added to the result list.
- Reverse the result list obtained in step 4 to obtain the longest increasing sublist.
Python3
def longest_alphabetic_order(list_, k): n = len(list_) lengths = [1] * n for i in range(1, n): if list_[i][k] >= list_[i-1][k]: lengths[i] = lengths[i-1] + 1 end_index = lengths.index(max(lengths)) result = [] current_length = max(lengths) for i in range(end_index, -1, -1): if lengths[i] == current_length: result.insert(0, list_[i]) current_length -= 1 return resultlist_ = ["gfg", "is", "best", "for", "neveropen", "and", "cs"]k = 1print(longest_alphabetic_order(list_, k)) # Output: ['best', 'cs', 'for', 'neveropen'] |
['neveropen', 'and', 'cs']
Time complexity: O(n^2)
Auxiliary space: O(n)
