Printing longest subsequence of letters using Python

print longest common subsequence python
longest common subsequence dynamic programming code
longest increasing subsequence
longest common subsequence python library
longest common subsequence javascript
longest common subsequence pseudocode
print longest common subsequence leetcode
longest common substring

Write a block of code to print the longest subsequence of letters out of an input string. - First, ask user to input any string. - You code should print the longest sub-string of the input string, which contains only letters of the English alphabet, including both uppercase and lowercase letters.

If there are multiple subsequences of the same longest length, the code returns the first one. If input_str doesn’t contain any letter, the function returns an empty string.

For example,

  • for input string 'ab24[AaBbCDExy0longest]', it should print 'AaBbCDExy'.

  • for input string 'a a a1234b|c|d ', it should print 'a'.

  • for input string '12345 ', it should print "" (empty string).

Tried the following code but in vain:

# Your code here

#longest_letterSeq = '' 
def longestSubstring(s): 
    longest_letterSeq = '' 
    i = 0
    while(i<len(s)): 

        curr_letterSeq = '' 

        # For letter substring  
        while(i<len(s) and s[i].isalpha()): 
            curr_letterSeq += s[i] 
            i+= 1

        # Case handling if the character is not letter     
            if(i< len(s) and not(s[i].isalpha())) : 
                i+= 1

            if(len(curr_letterSeq) > len(longest_letterSeq) ): 
                longest_letterSeq = curr_letterSeq 

    return longest_letterSeq

str = input("Please input your string here: ")

print(longestSubstring(str))

Can someone help with the edited or correct code?

One option is using re.findall with max:

import re
max(re.findall('[a-zA-Z]+',  'ab24[AaBbCDExy0longest]'), key=len)
# 'AaBbCDExy'

max(re.findall('[a-zA-Z]+', 'a a a1234b|c|d '), key=len)
# 'a'

Small hack to contemplate cases where there are no matches:

max(re.findall('[a-zA-Z]+', '12345 ') or [''], key=len)
# ''

Though I'd suggest you to go with the more readable approach:

r = re.findall('[a-zA-Z]+', '12345 ') 
if r:
    out = max(r, key=len)
else:
    out = ''

Or as @deepstop suggests with the conditional expression:

out = max(r, key=len) if r else ''

Printing Longest Common Subsequence, In this post we will discuss how to print Longest Common Subsequence itself. If the current characters in X and Y are equal (shown in bold), then they are part to post code in comments using C, C++, Java, Python, JavaScript, C#, PHP and  The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, the length of LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80} is 6 and LIS is {10, 22, 33, 50, 60, 80}.

like yatu, my first though on such a problem would be regex. However I have offered a solution based on your approach. the problem in your code is that you only increment i when the character is an alpha. So for the string abc123 you will increment i 3 times. but as the next char is not alpha you dont incerase i. which means i is now stuck with a value of 3 and thats less than the length of the string 6. so your function is stuck in an infinite loop since you stop increasing i.

A simplified version of your code can be written as below. essentially there is no need for a second while loop. Infact there is no need for a while loop at all, you can just use a for loop to iterate over each character in the string

def longestSubstring(string):
    longest_letterSeq = ''
    curr_letterSeq = ''
    for char in string:
        if char.isalpha():
            curr_letterSeq += char
        else:
            if len(curr_letterSeq) > len(longest_letterSeq):
                longest_letterSeq = curr_letterSeq
            curr_letterSeq = ''
    return longest_letterSeq

my_strings = ['ab24[AaBbCDExy0longest]', 'a a a1234b|c|d ', '12345']
for string in my_strings:
    longest = longestSubstring(string)
    print(f'the longest string in "{string}" is "{longest}"')

OUTPUT

the longest string in "ab24[AaBbCDExy0longest]" is "AaBbCDExy"
the longest string in "a a a1234b|c|d " is "a"
the longest string in "12345" is ""

Python Program for Longest Common Subsequence, The idea is very similar to printing Longest Common Subsequence(LCS) of two strings. Refer this post for details. C++; Java; Python. C++. Given two sequences, print the longest subsequence present in both of them. Examples: LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3. LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4. We have discussed Longest Common Subsequence (LCS) problem in a previous post.

An alternative approach is to replace all non-letters with a space, split, and then choose the longest string.

import re

def func(s) :
    l = re.sub('[^a-zA-Z]+', ' ', s).split()
    l.append('')  # Append an empty string so the list is bound not to be empty.
    return max(l, key=len)

func('ab24[AaBbCDExy0longest]')
func('foo2bar')
func('')

Longest Common Subsequence, For each character in s1(outer loop) select all the characters in s2(inner loop) c. create a character array LCS[] to print the longest common subsequence. 3. Print Longest substring without repeating characters; Check if sum of Fibonacci elements in an Array is a Fibonacci number or not; Count of subarrays having exactly K perfect square numbers; Check if given words are present in a string; Kth most frequent Character in a given String; Sorting a Map by value in C++ STL; LRU Cache in Python using

Longest Repeated Subsequence Problem, Python Program to find Longest Common Subsequence using Dynamic of a string s if r can be obtained from s by dropping zero or more characters from s. A string r is a longest common subsequence (LCS) of s and t if there is no i, j + 1)) c[i][j] = q return q def print_lcs(u, v, c): """Print one LCS of u and v using table c. How to print the subsequence? The above solution only finds length of subsequence. We can print the subsequence using dp[n+1][n+1] table built. The idea is similar to printing LCS. // Pseudo code to find longest repeated // subsequence using the dp[][] table filled // above.

Print Longest common subsequence, The longest common subsequence (LCS) is defined as the The longest you will understand the working of LCS with working code in C, C++, Java, and Python. If the character correspoding to the current row and current column are 1 elif L[i-1][j] > L[i][j-1]: i -= 1 else: j -= 1 # Printing the sub sequences print("S1 : " + S1  The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, the length of LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80} is 6 and LIS is {10, 22, 33, 50, 60, 80}.

Python Program to find Longest Common Subsequence using , What is Longest Common Subsequence: A longest subsequence is a add 1 to the result and remove the last character from both the strings and make recursive call to the modified strings. Complete Code( Include Printing Result): Python Basic - 1: Exercise-65 with Solution. In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Comments
  • Should be key=len on the 3rd line of the last example, or just out = max(r, key=len) if r else ''
  • Yes thanks @Deepstop . Yes just wanted to go for a more readable one for OP. Thanks anyways, lets add that too
  • NP. I thought as much.