human
Length of longest increasing subsequence in a string | Function to find length of longest increasing subsequence in a string.
Stores at every i - th index , the length of the longest increasing subsequence ending with character i.
Size of string.
Stores the length of LIS.
Iterate over each character of the string.
Store position of the current character.
Stores the length of LIS ending with current character.
Check for all characters less then current character.
Include current character.
Update length of longest increasing subsequence.
Updating LIS for current character.
Return the length of LIS.
Driver Code"
How can the above be solved in Python?
assistant
#Here is code to length of longest increasing subsequence in a string and the other steps required.
 def lisOtimised ( s ) :
	dp = [ 0 ] * 30
	N = len ( s )
	lis = - 10 ** 9
	for i in range ( N ) :
		val = ord ( s [ i ] ) - ord ( ' a ' )
		curr = 0
		for j in range ( val ) :
			curr = max ( curr , dp [ j ] )
		curr += 1
		lis = max ( lis , curr )
		dp [ val ] = max ( dp [ val ] , curr )
	return lis
if __name__ == ' _ _ main _ _ ' :
	s = " fdryutiaghfse "
	print ( lisOtimised ( s ) )