Mixing
Longest Ordered Subsequence of Vowels - Dynamic Programming
1
Given a string consisting of only vowels, find the longest subsequence in the given string such that it consists of all five vowels and is a sequence of one or more a’s, followed by one or more e’s, followed by one or more i’s, followed by one or more o’s and followed by one or more u’s.
If there is more than one longest subsequence, print any one.
QUESTION: can u pls show how u would add memoization to soln below/show how to solve using dp? I've seen how to solve recursively (below). I'm asking for help in arriving at dp soln.
Examples:
Input : str = "aeiaaioooaauuaeiou"
Output : {a, a, a, a, a, a, e, i, o, u}
There are two possible outputs in this case:
{a, a, a, a, a, a, e, i, o, u} and,
{a, e, i, i, o, o, o, u, u, u}
each of length 10
Input : str = "aaauuiieeou"
Output : No subsequence possible
Approach:
We loop through all the characters in the string recursively and follow the given conditions:
If the subsequence is empty, we include the vowel at the current index only if it is ‘a’. Otherwise, we move on to the next index.
If the vowel at the current index is same as the last vowel included in the subsequence, we include it.
If the vowel at the current index is the next possible vowel (i.e a–> e–> i–> o–> u ) after the last vowel included in the subsequence, we have two options: either include it or move on to the next index. Hence we choose the one which gives the longest subsequence.
If none of the above conditions is satisfied, we move on to the next index (to avoid invalid ordering of vowels in the subsequence).
If we have reached the end of the string, we check if the current subsequence is valid or not. If it is valid (i.e if it contains all the vowels), we return it, else we return an empty list.
# Python3 program to find the longest subsequence
# of vowels in the specified order
vowels = ['a', 'e', 'i', 'o', 'u']
# Mapping values for vowels
mapping = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}
# Function to check if given subsequence
# contains all the vowels or not
def isValidSequence(subList):
for vowel in vowels:
if vowel not in subList:
return False
return True
# Function to find the longest subsequence of vowels
# in the given string in specified order
def longestSubsequence(string, subList, index):
# If we have reached the end of the string,
# return the subsequence
# if it is valid, else return an empty list
if index == len(string):
if isValidSequence(subList) == True:
return subList
else:
return
else:
# If there is no vowel in the subsequence yet,
# add vowel at current index if it is 'a',
# else move on to the next character
# in the string
if len(subList) == 0:
if string[index] != 'a':
return longestSubsequence(string, subList, index + 1)
else:
return longestSubsequence(string, subList +
[string[index]], index + 1)
# If the last vowel in the subsequence until
# now is same as the vowel at current index,
# add it to the subsequence
elif mapping[subList[-1]] == mapping[string[index]]:
return longestSubsequence(string, subList +
[string[index]], index + 1)
# If the vowel at the current index comes
# right after the last vowel
# in the subsequence, we have two options:
# either to add the vowel in
# the subsequence, or move on to next character.
# We choose the one which gives the longest subsequence.
elif (mapping[subList[-1]] + 1) == mapping[string[index]]:
sub1 = longestSubsequence(string, subList +
[string[index]], index + 1)
sub2 = longestSubsequence(string, subList, index + 1)
if len(sub1) > len(sub2):
return sub1
else:
return sub2
else:
return longestSubsequence(string, subList, index + 1)
# Driver Code
if __name__ == "__main__":
string = "aeiaaioooauuaeiou"
subsequence = longestSubsequence(string, , 0)
if len(subsequence) == 0:
print("No subsequence possible")
else:
print(subsequence)
Output:
['a', 'e', 'i', 'i', 'o', 'o', 'o', 'u', 'u', 'u']
recursion dynamic-programming memoization subsequence
asked Jan 1 at 20:05
ModeldayModelday
336
add a comment |
1
Given a string consisting of only vowels, find the longest subsequence in the given string such that it consists of all five vowels and is a sequence of one or more a’s, followed by one or more e’s, followed by one or more i’s, followed by one or more o’s and followed by one or more u’s.
If there is more than one longest subsequence, print any one.
QUESTION: can u pls show how u would add memoization to soln below/show how to solve using dp? I've seen how to solve recursively (below). I'm asking for help in arriving at dp soln.
Examples:
Input : str = "aeiaaioooaauuaeiou"
Output : {a, a, a, a, a, a, e, i, o, u}
There are two possible outputs in this case:
{a, a, a, a, a, a, e, i, o, u} and,
{a, e, i, i, o, o, o, u, u, u}
each of length 10
Input : str = "aaauuiieeou"
Output : No subsequence possible
Approach:
We loop through all the characters in the string recursively and follow the given conditions:
If the subsequence is empty, we include the vowel at the current index only if it is ‘a’. Otherwise, we move on to the next index.
If the vowel at the current index is same as the last vowel included in the subsequence, we include it.
If the vowel at the current index is the next possible vowel (i.e a–> e–> i–> o–> u ) after the last vowel included in the subsequence, we have two options: either include it or move on to the next index. Hence we choose the one which gives the longest subsequence.
If none of the above conditions is satisfied, we move on to the next index (to avoid invalid ordering of vowels in the subsequence).
If we have reached the end of the string, we check if the current subsequence is valid or not. If it is valid (i.e if it contains all the vowels), we return it, else we return an empty list.
# Python3 program to find the longest subsequence
# of vowels in the specified order
vowels = ['a', 'e', 'i', 'o', 'u']
# Mapping values for vowels
mapping = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}
# Function to check if given subsequence
# contains all the vowels or not
def isValidSequence(subList):
for vowel in vowels:
if vowel not in subList:
return False
return True
# Function to find the longest subsequence of vowels
# in the given string in specified order
def longestSubsequence(string, subList, index):
# If we have reached the end of the string,
# return the subsequence
# if it is valid, else return an empty list
if index == len(string):
if isValidSequence(subList) == True:
return subList
else:
return
else:
# If there is no vowel in the subsequence yet,
# add vowel at current index if it is 'a',
# else move on to the next character
# in the string
if len(subList) == 0:
if string[index] != 'a':
return longestSubsequence(string, subList, index + 1)
else:
return longestSubsequence(string, subList +
[string[index]], index + 1)
# If the last vowel in the subsequence until
# now is same as the vowel at current index,
# add it to the subsequence
elif mapping[subList[-1]] == mapping[string[index]]:
return longestSubsequence(string, subList +
[string[index]], index + 1)
# If the vowel at the current index comes
# right after the last vowel
# in the subsequence, we have two options:
# either to add the vowel in
# the subsequence, or move on to next character.
# We choose the one which gives the longest subsequence.
elif (mapping[subList[-1]] + 1) == mapping[string[index]]:
sub1 = longestSubsequence(string, subList +
[string[index]], index + 1)
sub2 = longestSubsequence(string, subList, index + 1)
if len(sub1) > len(sub2):
return sub1
else:
return sub2
else:
return longestSubsequence(string, subList, index + 1)
# Driver Code
if __name__ == "__main__":
string = "aeiaaioooauuaeiou"
subsequence = longestSubsequence(string, , 0)
if len(subsequence) == 0:
print("No subsequence possible")
else:
print(subsequence)
Output:
['a', 'e', 'i', 'i', 'o', 'o', 'o', 'u', 'u', 'u']
recursion dynamic-programming memoization subsequence
asked Jan 1 at 20:05
ModeldayModelday
336
add a comment |
1
1
1
Given a string consisting of only vowels, find the longest subsequence in the given string such that it consists of all five vowels and is a sequence of one or more a’s, followed by one or more e’s, followed by one or more i’s, followed by one or more o’s and followed by one or more u’s.
If there is more than one longest subsequence, print any one.
QUESTION: can u pls show how u would add memoization to soln below/show how to solve using dp? I've seen how to solve recursively (below). I'm asking for help in arriving at dp soln.
Examples:
Input : str = "aeiaaioooaauuaeiou"
Output : {a, a, a, a, a, a, e, i, o, u}
There are two possible outputs in this case:
{a, a, a, a, a, a, e, i, o, u} and,
{a, e, i, i, o, o, o, u, u, u}
each of length 10
Input : str = "aaauuiieeou"
Output : No subsequence possible
Approach:
We loop through all the characters in the string recursively and follow the given conditions:
If the subsequence is empty, we include the vowel at the current index only if it is ‘a’. Otherwise, we move on to the next index.
If the vowel at the current index is same as the last vowel included in the subsequence, we include it.
If the vowel at the current index is the next possible vowel (i.e a–> e–> i–> o–> u ) after the last vowel included in the subsequence, we have two options: either include it or move on to the next index. Hence we choose the one which gives the longest subsequence.
If none of the above conditions is satisfied, we move on to the next index (to avoid invalid ordering of vowels in the subsequence).
If we have reached the end of the string, we check if the current subsequence is valid or not. If it is valid (i.e if it contains all the vowels), we return it, else we return an empty list.
# Python3 program to find the longest subsequence
# of vowels in the specified order
vowels = ['a', 'e', 'i', 'o', 'u']
# Mapping values for vowels
mapping = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}
# Function to check if given subsequence
# contains all the vowels or not
def isValidSequence(subList):
for vowel in vowels:
if vowel not in subList:
return False
return True
# Function to find the longest subsequence of vowels
# in the given string in specified order
def longestSubsequence(string, subList, index):
# If we have reached the end of the string,
# return the subsequence
# if it is valid, else return an empty list
if index == len(string):
if isValidSequence(subList) == True:
return subList
else:
return
else:
# If there is no vowel in the subsequence yet,
# add vowel at current index if it is 'a',
# else move on to the next character
# in the string
if len(subList) == 0:
if string[index] != 'a':
return longestSubsequence(string, subList, index + 1)
else:
return longestSubsequence(string, subList +
[string[index]], index + 1)
# If the last vowel in the subsequence until
# now is same as the vowel at current index,
# add it to the subsequence
elif mapping[subList[-1]] == mapping[string[index]]:
return longestSubsequence(string, subList +
[string[index]], index + 1)
# If the vowel at the current index comes
# right after the last vowel
# in the subsequence, we have two options:
# either to add the vowel in
# the subsequence, or move on to next character.
# We choose the one which gives the longest subsequence.
elif (mapping[subList[-1]] + 1) == mapping[string[index]]:
sub1 = longestSubsequence(string, subList +
[string[index]], index + 1)
sub2 = longestSubsequence(string, subList, index + 1)
if len(sub1) > len(sub2):
return sub1
else:
return sub2
else:
return longestSubsequence(string, subList, index + 1)
# Driver Code
if __name__ == "__main__":
string = "aeiaaioooauuaeiou"
subsequence = longestSubsequence(string, , 0)
if len(subsequence) == 0:
print("No subsequence possible")
else:
print(subsequence)
Output:
['a', 'e', 'i', 'i', 'o', 'o', 'o', 'u', 'u', 'u']
recursion dynamic-programming memoization subsequence
asked Jan 1 at 20:05
ModeldayModelday
336
Given a string consisting of only vowels, find the longest subsequence in the given string such that it consists of all five vowels and is a sequence of one or more a’s, followed by one or more e’s, followed by one or more i’s, followed by one or more o’s and followed by one or more u’s.
If there is more than one longest subsequence, print any one.
QUESTION: can u pls show how u would add memoization to soln below/show how to solve using dp? I've seen how to solve recursively (below). I'm asking for help in arriving at dp soln.
Examples:
Input : str = "aeiaaioooaauuaeiou"
Output : {a, a, a, a, a, a, e, i, o, u}
There are two possible outputs in this case:
{a, a, a, a, a, a, e, i, o, u} and,
{a, e, i, i, o, o, o, u, u, u}
each of length 10
Input : str = "aaauuiieeou"
Output : No subsequence possible
Approach:
We loop through all the characters in the string recursively and follow the given conditions:
If the subsequence is empty, we include the vowel at the current index only if it is ‘a’. Otherwise, we move on to the next index.
If the vowel at the current index is same as the last vowel included in the subsequence, we include it.
If the vowel at the current index is the next possible vowel (i.e a–> e–> i–> o–> u ) after the last vowel included in the subsequence, we have two options: either include it or move on to the next index. Hence we choose the one which gives the longest subsequence.
If none of the above conditions is satisfied, we move on to the next index (to avoid invalid ordering of vowels in the subsequence).
If we have reached the end of the string, we check if the current subsequence is valid or not. If it is valid (i.e if it contains all the vowels), we return it, else we return an empty list.
# Python3 program to find the longest subsequence
# of vowels in the specified order
vowels = ['a', 'e', 'i', 'o', 'u']
# Mapping values for vowels
mapping = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}
# Function to check if given subsequence
# contains all the vowels or not
def isValidSequence(subList):
for vowel in vowels:
if vowel not in subList:
return False
return True
# Function to find the longest subsequence of vowels
# in the given string in specified order
def longestSubsequence(string, subList, index):
# If we have reached the end of the string,
# return the subsequence
# if it is valid, else return an empty list
if index == len(string):
if isValidSequence(subList) == True:
return subList
else:
return
else:
# If there is no vowel in the subsequence yet,
# add vowel at current index if it is 'a',
# else move on to the next character
# in the string
if len(subList) == 0:
if string[index] != 'a':
return longestSubsequence(string, subList, index + 1)
else:
return longestSubsequence(string, subList +
[string[index]], index + 1)
# If the last vowel in the subsequence until
# now is same as the vowel at current index,
# add it to the subsequence
elif mapping[subList[-1]] == mapping[string[index]]:
return longestSubsequence(string, subList +
[string[index]], index + 1)
# If the vowel at the current index comes
# right after the last vowel
# in the subsequence, we have two options:
# either to add the vowel in
# the subsequence, or move on to next character.
# We choose the one which gives the longest subsequence.
elif (mapping[subList[-1]] + 1) == mapping[string[index]]:
sub1 = longestSubsequence(string, subList +
[string[index]], index + 1)
sub2 = longestSubsequence(string, subList, index + 1)
if len(sub1) > len(sub2):
return sub1
else:
return sub2
else:
return longestSubsequence(string, subList, index + 1)
# Driver Code
if __name__ == "__main__":
string = "aeiaaioooauuaeiou"
subsequence = longestSubsequence(string, , 0)
if len(subsequence) == 0:
print("No subsequence possible")
else:
print(subsequence)
Output:
['a', 'e', 'i', 'i', 'o', 'o', 'o', 'u', 'u', 'u']
recursion dynamic-programming memoization subsequence
recursion dynamic-programming memoization subsequence
asked Jan 1 at 20:05
ModeldayModelday
336
asked Jan 1 at 20:05
ModeldayModelday
336
asked Jan 1 at 20:05
ModeldayModelday
336
asked Jan 1 at 20:05
ModeldayModelday
336
asked Jan 1 at 20:05
ModeldayModelday
336
336
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
1
The key realization for memoizing your function is that you can use (last_chosen_char, length, index) as your memo key. In other words, treat "aaeeeiiioo", i=15 and "aaaaaaaeio", i=15 as identical, because their last chosen characters, lengths and current indices are equivalent. The subproblems of both calls will have identical solutions and we only need to bother computing one of them.
A few additional remarks:
- Avoid global variables which break encapsulation of your functions, which should work as black boxes and not have external dependencies.
- Use default parameters or a helper function to hide unnecessary parameters from the caller and offer a clean interface.
- Since lists aren't hashable (because they're mutable), I switched to using strings.
- After memoization, your call stack is the new bottleneck. You can consider using loops to collect series of duplicates. Similarly, once you've chosen a
"u", you might as well loop and collect all remaining"u"s in the string; there are no more decisions to be made. You might wish to pre-process the input string a bit to prune off more of the call stack. For example, record the next char position for each index and bail early once you've hit the last"u". None of this would help the worst case, though, so rewriting the logic iteratively using a bottom-up approach would be optimal.
Putting it together, you can now input strings up to the length of the stack size:
def longest_subsequence(string):
def helper(chosen="", i=0):
if i == len(string):
return chosen if set("aeiou").issubset(set(chosen)) else ""
hashable = (chosen[-1] if chosen else None, len(chosen), i)
if hashable in memo:
return memo[hashable]
if not chosen:
res = helper("a" if string[i] == "a" else chosen, i + 1)
elif chosen[-1] == string[i]:
res = helper(chosen + string[i], i + 1)
elif mapping[chosen[-1]] + 1 == mapping[string[i]]:
sub1 = helper(chosen + string[i], i + 1)
sub2 = helper(chosen, i + 1)
res = sub1 if len(sub1) > len(sub2) else sub2
else:
res = helper(chosen, i + 1)
memo[hashable] = res
return res
mapping = {x: i for i, x in enumerate("aeiou")}
memo = {}
return helper()
Here's an example run on a string of 900 characters:
original: uouoouiuoueaeeiiiaaaouuuueuaiaeaioaaiouaouiaiiaiuuueaueaieeueeuuouioaoaeueoioeoeioiuiaiaoeuuuuauuaiuueiieaauuoieiuoiaiueeeoaeaueaaaiaiiieuaoaiaaoiaoaueouaiiooaeeoioiaoieouuuoeaoaeeaaiuieouaeeooiiuooeauueaoaoaeuoaieauooueeeuiueuaeoeouuuiaoiauiaoiaaeeoeouuuueuiiuueoeeoiieuuuauooeuuaaaueuaaaaoaieaiiuoaoouueeeooiuoieoaueooaaioaeoiiiauuoeiaioeauaueiiaeoueioeiieuoiueoeoueeiuiooaioeooueuioaoaeoaiiiauoooieueoeauaiauauuauoueeauouieeoeoeiaeeeeooooeoaueouuuuiioeeuioueeuiaiueooeueeuuuoooeeuooeuoeeeaiioeeiioauiaeaiuaiauooiioeoeueoeieuueouaeeuuoeuaueeeauiiaoeeaeuieoeiuoooeaeeiuaiauuieouuuiuouiuieieoueiiaoiuioaiououooieiauuuououuiiiuaoeeieueeiuoeiaouoeueieuoiaeuoeiieeeaaaeiaeeoauoaoeuuoiiaaeiuiouueaoeuueeoouiaeeeouiouaaaeiouaaeauauioeoeuiauaeaououoaiuuueuieiaeeaouuueeaaiauoieoioaoiuuaioaiauioueieuuuueiaeeuaoeeoeioeoaiauiiuaouuoouooouaeueaioiaouuiiuauiaaeooeueiuoiuoeeauueuuueuueouiiauiuaoiuuoeuoeeauaeoo
max subsequence: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeiiiiiiiiiiiooooouuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu
Try it!
answered Jan 5 at 0:09
ggorlenggorlen
7,5033826
"(last_chosen_char, length, index) as your memo key." even if they r not of same length, The subsequent calls of both will have identical solutions if just last_chosen_char and index same ya? given "aeeeiiioo", i=*14* and "aaaaaaaeio", i=15, we can memoize the subsequent calls after "o" using just (last_chosen_char, index), append to both prefixes, and see which is longer ya? or we can even only compute for the prefix that currently has longer length and ignore the prefix of shorter length ya?
– Modelday
Jan 6 at 21:15
thank u ggorlen! "After memoization, your call stack is the new bottleneck." Right, for example if I see the same string @ a greater index, I know result from lesser index will be greater or equal to result from greater index, yes? E.g. if i call helper("aee", 7) and helper("aee", 9), result of helper("aee", 7) >= result of helper("aee", 9).
– Modelday
Jan 6 at 21:18
1
It's tempting to want to make the memo keys broader so you get more cache hits--I tried that myself in the course of writing this answer. But if you create a false equivalence between two states that are actually distinct, you compromise correctness, which omitting the length does. Try it out and see. As for your second remark, I don't quite follow, but what I mean by recursion as bottleneck is that each char basically has to have its own function call. If the stack size is 1000, the biggest string you can process is 999 or so (includingmain). So the next step is writing this iteratively.
– ggorlen
Jan 6 at 23:25
1
Upper bound, yes O(2^n), because worst case you hit the double branch on every char and create 2 recursive calls. For Java, I would multiply the ASCII value of thelast_chosen_charby some prime number and do similar for thelengthandindexand sum them. It's not surprising you're not getting hits on a short string like that and it's not going to save much work anyway. There may be a way to improve the key efficiency to generate more hits, but the important thing is correctness. I haven't thought a lot about a bottom-up iterative DP on this one, but if I have time I'll try to code it.
– ggorlen
Jan 8 at 2:32
1
Also useful for hashing in Java
– ggorlen
Jan 8 at 2:46
|
show 12 more comments
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53998563%2flongest-ordered-subsequence-of-vowels-dynamic-programming%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
1
The key realization for memoizing your function is that you can use (last_chosen_char, length, index) as your memo key. In other words, treat "aaeeeiiioo", i=15 and "aaaaaaaeio", i=15 as identical, because their last chosen characters, lengths and current indices are equivalent. The subproblems of both calls will have identical solutions and we only need to bother computing one of them.
A few additional remarks:
- Avoid global variables which break encapsulation of your functions, which should work as black boxes and not have external dependencies.
- Use default parameters or a helper function to hide unnecessary parameters from the caller and offer a clean interface.
- Since lists aren't hashable (because they're mutable), I switched to using strings.
- After memoization, your call stack is the new bottleneck. You can consider using loops to collect series of duplicates. Similarly, once you've chosen a
"u", you might as well loop and collect all remaining"u"s in the string; there are no more decisions to be made. You might wish to pre-process the input string a bit to prune off more of the call stack. For example, record the next char position for each index and bail early once you've hit the last"u". None of this would help the worst case, though, so rewriting the logic iteratively using a bottom-up approach would be optimal.
Putting it together, you can now input strings up to the length of the stack size:
def longest_subsequence(string):
def helper(chosen="", i=0):
if i == len(string):
return chosen if set("aeiou").issubset(set(chosen)) else ""
hashable = (chosen[-1] if chosen else None, len(chosen), i)
if hashable in memo:
return memo[hashable]
if not chosen:
res = helper("a" if string[i] == "a" else chosen, i + 1)
elif chosen[-1] == string[i]:
res = helper(chosen + string[i], i + 1)
elif mapping[chosen[-1]] + 1 == mapping[string[i]]:
sub1 = helper(chosen + string[i], i + 1)
sub2 = helper(chosen, i + 1)
res = sub1 if len(sub1) > len(sub2) else sub2
else:
res = helper(chosen, i + 1)
memo[hashable] = res
return res
mapping = {x: i for i, x in enumerate("aeiou")}
memo = {}
return helper()
Here's an example run on a string of 900 characters:
original: uouoouiuoueaeeiiiaaaouuuueuaiaeaioaaiouaouiaiiaiuuueaueaieeueeuuouioaoaeueoioeoeioiuiaiaoeuuuuauuaiuueiieaauuoieiuoiaiueeeoaeaueaaaiaiiieuaoaiaaoiaoaueouaiiooaeeoioiaoieouuuoeaoaeeaaiuieouaeeooiiuooeauueaoaoaeuoaieauooueeeuiueuaeoeouuuiaoiauiaoiaaeeoeouuuueuiiuueoeeoiieuuuauooeuuaaaueuaaaaoaieaiiuoaoouueeeooiuoieoaueooaaioaeoiiiauuoeiaioeauaueiiaeoueioeiieuoiueoeoueeiuiooaioeooueuioaoaeoaiiiauoooieueoeauaiauauuauoueeauouieeoeoeiaeeeeooooeoaueouuuuiioeeuioueeuiaiueooeueeuuuoooeeuooeuoeeeaiioeeiioauiaeaiuaiauooiioeoeueoeieuueouaeeuuoeuaueeeauiiaoeeaeuieoeiuoooeaeeiuaiauuieouuuiuouiuieieoueiiaoiuioaiououooieiauuuououuiiiuaoeeieueeiuoeiaouoeueieuoiaeuoeiieeeaaaeiaeeoauoaoeuuoiiaaeiuiouueaoeuueeoouiaeeeouiouaaaeiouaaeauauioeoeuiauaeaououoaiuuueuieiaeeaouuueeaaiauoieoioaoiuuaioaiauioueieuuuueiaeeuaoeeoeioeoaiauiiuaouuoouooouaeueaioiaouuiiuauiaaeooeueiuoiuoeeauueuuueuueouiiauiuaoiuuoeuoeeauaeoo
max subsequence: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeiiiiiiiiiiiooooouuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu
Try it!
answered Jan 5 at 0:09
ggorlenggorlen
7,5033826
"(last_chosen_char, length, index) as your memo key." even if they r not of same length, The subsequent calls of both will have identical solutions if just last_chosen_char and index same ya? given "aeeeiiioo", i=*14* and "aaaaaaaeio", i=15, we can memoize the subsequent calls after "o" using just (last_chosen_char, index), append to both prefixes, and see which is longer ya? or we can even only compute for the prefix that currently has longer length and ignore the prefix of shorter length ya?
– Modelday
Jan 6 at 21:15
thank u ggorlen! "After memoization, your call stack is the new bottleneck." Right, for example if I see the same string @ a greater index, I know result from lesser index will be greater or equal to result from greater index, yes? E.g. if i call helper("aee", 7) and helper("aee", 9), result of helper("aee", 7) >= result of helper("aee", 9).
– Modelday
Jan 6 at 21:18
1
It's tempting to want to make the memo keys broader so you get more cache hits--I tried that myself in the course of writing this answer. But if you create a false equivalence between two states that are actually distinct, you compromise correctness, which omitting the length does. Try it out and see. As for your second remark, I don't quite follow, but what I mean by recursion as bottleneck is that each char basically has to have its own function call. If the stack size is 1000, the biggest string you can process is 999 or so (includingmain). So the next step is writing this iteratively.
– ggorlen
Jan 6 at 23:25
1
Upper bound, yes O(2^n), because worst case you hit the double branch on every char and create 2 recursive calls. For Java, I would multiply the ASCII value of thelast_chosen_charby some prime number and do similar for thelengthandindexand sum them. It's not surprising you're not getting hits on a short string like that and it's not going to save much work anyway. There may be a way to improve the key efficiency to generate more hits, but the important thing is correctness. I haven't thought a lot about a bottom-up iterative DP on this one, but if I have time I'll try to code it.
– ggorlen
Jan 8 at 2:32
1
Also useful for hashing in Java
– ggorlen
Jan 8 at 2:46
|
show 12 more comments
1
The key realization for memoizing your function is that you can use (last_chosen_char, length, index) as your memo key. In other words, treat "aaeeeiiioo", i=15 and "aaaaaaaeio", i=15 as identical, because their last chosen characters, lengths and current indices are equivalent. The subproblems of both calls will have identical solutions and we only need to bother computing one of them.
A few additional remarks:
- Avoid global variables which break encapsulation of your functions, which should work as black boxes and not have external dependencies.
- Use default parameters or a helper function to hide unnecessary parameters from the caller and offer a clean interface.
- Since lists aren't hashable (because they're mutable), I switched to using strings.
- After memoization, your call stack is the new bottleneck. You can consider using loops to collect series of duplicates. Similarly, once you've chosen a
"u", you might as well loop and collect all remaining"u"s in the string; there are no more decisions to be made. You might wish to pre-process the input string a bit to prune off more of the call stack. For example, record the next char position for each index and bail early once you've hit the last"u". None of this would help the worst case, though, so rewriting the logic iteratively using a bottom-up approach would be optimal.
Putting it together, you can now input strings up to the length of the stack size:
def longest_subsequence(string):
def helper(chosen="", i=0):
if i == len(string):
return chosen if set("aeiou").issubset(set(chosen)) else ""
hashable = (chosen[-1] if chosen else None, len(chosen), i)
if hashable in memo:
return memo[hashable]
if not chosen:
res = helper("a" if string[i] == "a" else chosen, i + 1)
elif chosen[-1] == string[i]:
res = helper(chosen + string[i], i + 1)
elif mapping[chosen[-1]] + 1 == mapping[string[i]]:
sub1 = helper(chosen + string[i], i + 1)
sub2 = helper(chosen, i + 1)
res = sub1 if len(sub1) > len(sub2) else sub2
else:
res = helper(chosen, i + 1)
memo[hashable] = res
return res
mapping = {x: i for i, x in enumerate("aeiou")}
memo = {}
return helper()
Here's an example run on a string of 900 characters:
original: uouoouiuoueaeeiiiaaaouuuueuaiaeaioaaiouaouiaiiaiuuueaueaieeueeuuouioaoaeueoioeoeioiuiaiaoeuuuuauuaiuueiieaauuoieiuoiaiueeeoaeaueaaaiaiiieuaoaiaaoiaoaueouaiiooaeeoioiaoieouuuoeaoaeeaaiuieouaeeooiiuooeauueaoaoaeuoaieauooueeeuiueuaeoeouuuiaoiauiaoiaaeeoeouuuueuiiuueoeeoiieuuuauooeuuaaaueuaaaaoaieaiiuoaoouueeeooiuoieoaueooaaioaeoiiiauuoeiaioeauaueiiaeoueioeiieuoiueoeoueeiuiooaioeooueuioaoaeoaiiiauoooieueoeauaiauauuauoueeauouieeoeoeiaeeeeooooeoaueouuuuiioeeuioueeuiaiueooeueeuuuoooeeuooeuoeeeaiioeeiioauiaeaiuaiauooiioeoeueoeieuueouaeeuuoeuaueeeauiiaoeeaeuieoeiuoooeaeeiuaiauuieouuuiuouiuieieoueiiaoiuioaiououooieiauuuououuiiiuaoeeieueeiuoeiaouoeueieuoiaeuoeiieeeaaaeiaeeoauoaoeuuoiiaaeiuiouueaoeuueeoouiaeeeouiouaaaeiouaaeauauioeoeuiauaeaououoaiuuueuieiaeeaouuueeaaiauoieoioaoiuuaioaiauioueieuuuueiaeeuaoeeoeioeoaiauiiuaouuoouooouaeueaioiaouuiiuauiaaeooeueiuoiuoeeauueuuueuueouiiauiuaoiuuoeuoeeauaeoo
max subsequence: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeiiiiiiiiiiiooooouuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu
Try it!
answered Jan 5 at 0:09
ggorlenggorlen
7,5033826
"(last_chosen_char, length, index) as your memo key." even if they r not of same length, The subsequent calls of both will have identical solutions if just last_chosen_char and index same ya? given "aeeeiiioo", i=*14* and "aaaaaaaeio", i=15, we can memoize the subsequent calls after "o" using just (last_chosen_char, index), append to both prefixes, and see which is longer ya? or we can even only compute for the prefix that currently has longer length and ignore the prefix of shorter length ya?
– Modelday
Jan 6 at 21:15
thank u ggorlen! "After memoization, your call stack is the new bottleneck." Right, for example if I see the same string @ a greater index, I know result from lesser index will be greater or equal to result from greater index, yes? E.g. if i call helper("aee", 7) and helper("aee", 9), result of helper("aee", 7) >= result of helper("aee", 9).
– Modelday
Jan 6 at 21:18
1
It's tempting to want to make the memo keys broader so you get more cache hits--I tried that myself in the course of writing this answer. But if you create a false equivalence between two states that are actually distinct, you compromise correctness, which omitting the length does. Try it out and see. As for your second remark, I don't quite follow, but what I mean by recursion as bottleneck is that each char basically has to have its own function call. If the stack size is 1000, the biggest string you can process is 999 or so (includingmain). So the next step is writing this iteratively.
– ggorlen
Jan 6 at 23:25
1
Upper bound, yes O(2^n), because worst case you hit the double branch on every char and create 2 recursive calls. For Java, I would multiply the ASCII value of thelast_chosen_charby some prime number and do similar for thelengthandindexand sum them. It's not surprising you're not getting hits on a short string like that and it's not going to save much work anyway. There may be a way to improve the key efficiency to generate more hits, but the important thing is correctness. I haven't thought a lot about a bottom-up iterative DP on this one, but if I have time I'll try to code it.
– ggorlen
Jan 8 at 2:32
1
Also useful for hashing in Java
– ggorlen
Jan 8 at 2:46
|
show 12 more comments
1
1
1
The key realization for memoizing your function is that you can use (last_chosen_char, length, index) as your memo key. In other words, treat "aaeeeiiioo", i=15 and "aaaaaaaeio", i=15 as identical, because their last chosen characters, lengths and current indices are equivalent. The subproblems of both calls will have identical solutions and we only need to bother computing one of them.
A few additional remarks:
- Avoid global variables which break encapsulation of your functions, which should work as black boxes and not have external dependencies.
- Use default parameters or a helper function to hide unnecessary parameters from the caller and offer a clean interface.
- Since lists aren't hashable (because they're mutable), I switched to using strings.
- After memoization, your call stack is the new bottleneck. You can consider using loops to collect series of duplicates. Similarly, once you've chosen a
"u", you might as well loop and collect all remaining"u"s in the string; there are no more decisions to be made. You might wish to pre-process the input string a bit to prune off more of the call stack. For example, record the next char position for each index and bail early once you've hit the last"u". None of this would help the worst case, though, so rewriting the logic iteratively using a bottom-up approach would be optimal.
Putting it together, you can now input strings up to the length of the stack size:
def longest_subsequence(string):
def helper(chosen="", i=0):
if i == len(string):
return chosen if set("aeiou").issubset(set(chosen)) else ""
hashable = (chosen[-1] if chosen else None, len(chosen), i)
if hashable in memo:
return memo[hashable]
if not chosen:
res = helper("a" if string[i] == "a" else chosen, i + 1)
elif chosen[-1] == string[i]:
res = helper(chosen + string[i], i + 1)
elif mapping[chosen[-1]] + 1 == mapping[string[i]]:
sub1 = helper(chosen + string[i], i + 1)
sub2 = helper(chosen, i + 1)
res = sub1 if len(sub1) > len(sub2) else sub2
else:
res = helper(chosen, i + 1)
memo[hashable] = res
return res
mapping = {x: i for i, x in enumerate("aeiou")}
memo = {}
return helper()
Here's an example run on a string of 900 characters:
original: uouoouiuoueaeeiiiaaaouuuueuaiaeaioaaiouaouiaiiaiuuueaueaieeueeuuouioaoaeueoioeoeioiuiaiaoeuuuuauuaiuueiieaauuoieiuoiaiueeeoaeaueaaaiaiiieuaoaiaaoiaoaueouaiiooaeeoioiaoieouuuoeaoaeeaaiuieouaeeooiiuooeauueaoaoaeuoaieauooueeeuiueuaeoeouuuiaoiauiaoiaaeeoeouuuueuiiuueoeeoiieuuuauooeuuaaaueuaaaaoaieaiiuoaoouueeeooiuoieoaueooaaioaeoiiiauuoeiaioeauaueiiaeoueioeiieuoiueoeoueeiuiooaioeooueuioaoaeoaiiiauoooieueoeauaiauauuauoueeauouieeoeoeiaeeeeooooeoaueouuuuiioeeuioueeuiaiueooeueeuuuoooeeuooeuoeeeaiioeeiioauiaeaiuaiauooiioeoeueoeieuueouaeeuuoeuaueeeauiiaoeeaeuieoeiuoooeaeeiuaiauuieouuuiuouiuieieoueiiaoiuioaiououooieiauuuououuiiiuaoeeieueeiuoeiaouoeueieuoiaeuoeiieeeaaaeiaeeoauoaoeuuoiiaaeiuiouueaoeuueeoouiaeeeouiouaaaeiouaaeauauioeoeuiauaeaououoaiuuueuieiaeeaouuueeaaiauoieoioaoiuuaioaiauioueieuuuueiaeeuaoeeoeioeoaiauiiuaouuoouooouaeueaioiaouuiiuauiaaeooeueiuoiuoeeauueuuueuueouiiauiuaoiuuoeuoeeauaeoo
max subsequence: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeiiiiiiiiiiiooooouuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu
Try it!
answered Jan 5 at 0:09
ggorlenggorlen
7,5033826
The key realization for memoizing your function is that you can use (last_chosen_char, length, index) as your memo key. In other words, treat "aaeeeiiioo", i=15 and "aaaaaaaeio", i=15 as identical, because their last chosen characters, lengths and current indices are equivalent. The subproblems of both calls will have identical solutions and we only need to bother computing one of them.
A few additional remarks:
- Avoid global variables which break encapsulation of your functions, which should work as black boxes and not have external dependencies.
- Use default parameters or a helper function to hide unnecessary parameters from the caller and offer a clean interface.
- Since lists aren't hashable (because they're mutable), I switched to using strings.
- After memoization, your call stack is the new bottleneck. You can consider using loops to collect series of duplicates. Similarly, once you've chosen a
"u", you might as well loop and collect all remaining"u"s in the string; there are no more decisions to be made. You might wish to pre-process the input string a bit to prune off more of the call stack. For example, record the next char position for each index and bail early once you've hit the last"u". None of this would help the worst case, though, so rewriting the logic iteratively using a bottom-up approach would be optimal.
Putting it together, you can now input strings up to the length of the stack size:
def longest_subsequence(string):
def helper(chosen="", i=0):
if i == len(string):
return chosen if set("aeiou").issubset(set(chosen)) else ""
hashable = (chosen[-1] if chosen else None, len(chosen), i)
if hashable in memo:
return memo[hashable]
if not chosen:
res = helper("a" if string[i] == "a" else chosen, i + 1)
elif chosen[-1] == string[i]:
res = helper(chosen + string[i], i + 1)
elif mapping[chosen[-1]] + 1 == mapping[string[i]]:
sub1 = helper(chosen + string[i], i + 1)
sub2 = helper(chosen, i + 1)
res = sub1 if len(sub1) > len(sub2) else sub2
else:
res = helper(chosen, i + 1)
memo[hashable] = res
return res
mapping = {x: i for i, x in enumerate("aeiou")}
memo = {}
return helper()
Here's an example run on a string of 900 characters:
original: uouoouiuoueaeeiiiaaaouuuueuaiaeaioaaiouaouiaiiaiuuueaueaieeueeuuouioaoaeueoioeoeioiuiaiaoeuuuuauuaiuueiieaauuoieiuoiaiueeeoaeaueaaaiaiiieuaoaiaaoiaoaueouaiiooaeeoioiaoieouuuoeaoaeeaaiuieouaeeooiiuooeauueaoaoaeuoaieauooueeeuiueuaeoeouuuiaoiauiaoiaaeeoeouuuueuiiuueoeeoiieuuuauooeuuaaaueuaaaaoaieaiiuoaoouueeeooiuoieoaueooaaioaeoiiiauuoeiaioeauaueiiaeoueioeiieuoiueoeoueeiuiooaioeooueuioaoaeoaiiiauoooieueoeauaiauauuauoueeauouieeoeoeiaeeeeooooeoaueouuuuiioeeuioueeuiaiueooeueeuuuoooeeuooeuoeeeaiioeeiioauiaeaiuaiauooiioeoeueoeieuueouaeeuuoeuaueeeauiiaoeeaeuieoeiuoooeaeeiuaiauuieouuuiuouiuieieoueiiaoiuioaiououooieiauuuououuiiiuaoeeieueeiuoeiaouoeueieuoiaeuoeiieeeaaaeiaeeoauoaoeuuoiiaaeiuiouueaoeuueeoouiaeeeouiouaaaeiouaaeauauioeoeuiauaeaououoaiuuueuieiaeeaouuueeaaiauoieoioaoiuuaioaiauioueieuuuueiaeeuaoeeoeioeoaiauiiuaouuoouooouaeueaioiaouuiiuauiaaeooeueiuoiuoeeauueuuueuueouiiauiuaoiuuoeuoeeauaeoo
max subsequence: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeiiiiiiiiiiiooooouuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu
Try it!
answered Jan 5 at 0:09
ggorlenggorlen
7,5033826
edited Jan 5 at 0:50
answered Jan 5 at 0:09
ggorlenggorlen
7,5033826
answered Jan 5 at 0:09
ggorlenggorlen
7,5033826
answered Jan 5 at 0:09
ggorlenggorlen
7,5033826
7,5033826
"(last_chosen_char, length, index) as your memo key." even if they r not of same length, The subsequent calls of both will have identical solutions if just last_chosen_char and index same ya? given "aeeeiiioo", i=*14* and "aaaaaaaeio", i=15, we can memoize the subsequent calls after "o" using just (last_chosen_char, index), append to both prefixes, and see which is longer ya? or we can even only compute for the prefix that currently has longer length and ignore the prefix of shorter length ya?
– Modelday
Jan 6 at 21:15
thank u ggorlen! "After memoization, your call stack is the new bottleneck." Right, for example if I see the same string @ a greater index, I know result from lesser index will be greater or equal to result from greater index, yes? E.g. if i call helper("aee", 7) and helper("aee", 9), result of helper("aee", 7) >= result of helper("aee", 9).
– Modelday
Jan 6 at 21:18
1
It's tempting to want to make the memo keys broader so you get more cache hits--I tried that myself in the course of writing this answer. But if you create a false equivalence between two states that are actually distinct, you compromise correctness, which omitting the length does. Try it out and see. As for your second remark, I don't quite follow, but what I mean by recursion as bottleneck is that each char basically has to have its own function call. If the stack size is 1000, the biggest string you can process is 999 or so (includingmain). So the next step is writing this iteratively.
– ggorlen
Jan 6 at 23:25
1
Upper bound, yes O(2^n), because worst case you hit the double branch on every char and create 2 recursive calls. For Java, I would multiply the ASCII value of thelast_chosen_charby some prime number and do similar for thelengthandindexand sum them. It's not surprising you're not getting hits on a short string like that and it's not going to save much work anyway. There may be a way to improve the key efficiency to generate more hits, but the important thing is correctness. I haven't thought a lot about a bottom-up iterative DP on this one, but if I have time I'll try to code it.
– ggorlen
Jan 8 at 2:32
1
Also useful for hashing in Java
– ggorlen
Jan 8 at 2:46
|
show 12 more comments
"(last_chosen_char, length, index) as your memo key." even if they r not of same length, The subsequent calls of both will have identical solutions if just last_chosen_char and index same ya? given "aeeeiiioo", i=*14* and "aaaaaaaeio", i=15, we can memoize the subsequent calls after "o" using just (last_chosen_char, index), append to both prefixes, and see which is longer ya? or we can even only compute for the prefix that currently has longer length and ignore the prefix of shorter length ya?
– Modelday
Jan 6 at 21:15
thank u ggorlen! "After memoization, your call stack is the new bottleneck." Right, for example if I see the same string @ a greater index, I know result from lesser index will be greater or equal to result from greater index, yes? E.g. if i call helper("aee", 7) and helper("aee", 9), result of helper("aee", 7) >= result of helper("aee", 9).
– Modelday
Jan 6 at 21:18
1
It's tempting to want to make the memo keys broader so you get more cache hits--I tried that myself in the course of writing this answer. But if you create a false equivalence between two states that are actually distinct, you compromise correctness, which omitting the length does. Try it out and see. As for your second remark, I don't quite follow, but what I mean by recursion as bottleneck is that each char basically has to have its own function call. If the stack size is 1000, the biggest string you can process is 999 or so (includingmain). So the next step is writing this iteratively.
– ggorlen
Jan 6 at 23:25
1
Upper bound, yes O(2^n), because worst case you hit the double branch on every char and create 2 recursive calls. For Java, I would multiply the ASCII value of thelast_chosen_charby some prime number and do similar for thelengthandindexand sum them. It's not surprising you're not getting hits on a short string like that and it's not going to save much work anyway. There may be a way to improve the key efficiency to generate more hits, but the important thing is correctness. I haven't thought a lot about a bottom-up iterative DP on this one, but if I have time I'll try to code it.
– ggorlen
Jan 8 at 2:32
1
Also useful for hashing in Java
– ggorlen
Jan 8 at 2:46
"(last_chosen_char, length, index) as your memo key." even if they r not of same length, The subsequent calls of both will have identical solutions if just last_chosen_char and index same ya? given "aeeeiiioo", i=*14* and "aaaaaaaeio", i=15, we can memoize the subsequent calls after "o" using just (last_chosen_char, index), append to both prefixes, and see which is longer ya? or we can even only compute for the prefix that currently has longer length and ignore the prefix of shorter length ya?
– Modelday
Jan 6 at 21:15
"(last_chosen_char, length, index) as your memo key." even if they r not of same length, The subsequent calls of both will have identical solutions if just last_chosen_char and index same ya? given "aeeeiiioo", i=*14* and "aaaaaaaeio", i=15, we can memoize the subsequent calls after "o" using just (last_chosen_char, index), append to both prefixes, and see which is longer ya? or we can even only compute for the prefix that currently has longer length and ignore the prefix of shorter length ya?
– Modelday
Jan 6 at 21:15
thank u ggorlen! "After memoization, your call stack is the new bottleneck." Right, for example if I see the same string @ a greater index, I know result from lesser index will be greater or equal to result from greater index, yes? E.g. if i call helper("aee", 7) and helper("aee", 9), result of helper("aee", 7) >= result of helper("aee", 9).
– Modelday
Jan 6 at 21:18
thank u ggorlen! "After memoization, your call stack is the new bottleneck." Right, for example if I see the same string @ a greater index, I know result from lesser index will be greater or equal to result from greater index, yes? E.g. if i call helper("aee", 7) and helper("aee", 9), result of helper("aee", 7) >= result of helper("aee", 9).
– Modelday
Jan 6 at 21:18
1
1
It's tempting to want to make the memo keys broader so you get more cache hits--I tried that myself in the course of writing this answer. But if you create a false equivalence between two states that are actually distinct, you compromise correctness, which omitting the length does. Try it out and see. As for your second remark, I don't quite follow, but what I mean by recursion as bottleneck is that each char basically has to have its own function call. If the stack size is 1000, the biggest string you can process is 999 or so (including
main). So the next step is writing this iteratively.– ggorlen
Jan 6 at 23:25
It's tempting to want to make the memo keys broader so you get more cache hits--I tried that myself in the course of writing this answer. But if you create a false equivalence between two states that are actually distinct, you compromise correctness, which omitting the length does. Try it out and see. As for your second remark, I don't quite follow, but what I mean by recursion as bottleneck is that each char basically has to have its own function call. If the stack size is 1000, the biggest string you can process is 999 or so (including
main). So the next step is writing this iteratively.– ggorlen
Jan 6 at 23:25
1
1
Upper bound, yes O(2^n), because worst case you hit the double branch on every char and create 2 recursive calls. For Java, I would multiply the ASCII value of the
last_chosen_char by some prime number and do similar for the length and index and sum them. It's not surprising you're not getting hits on a short string like that and it's not going to save much work anyway. There may be a way to improve the key efficiency to generate more hits, but the important thing is correctness. I haven't thought a lot about a bottom-up iterative DP on this one, but if I have time I'll try to code it.– ggorlen
Jan 8 at 2:32
Upper bound, yes O(2^n), because worst case you hit the double branch on every char and create 2 recursive calls. For Java, I would multiply the ASCII value of the
last_chosen_char by some prime number and do similar for the length and index and sum them. It's not surprising you're not getting hits on a short string like that and it's not going to save much work anyway. There may be a way to improve the key efficiency to generate more hits, but the important thing is correctness. I haven't thought a lot about a bottom-up iterative DP on this one, but if I have time I'll try to code it.– ggorlen
Jan 8 at 2:32
1
1
Also useful for hashing in Java
– ggorlen
Jan 8 at 2:46
Also useful for hashing in Java
– ggorlen
Jan 8 at 2:46
|
show 12 more comments
draft saved
draft discarded
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53998563%2flongest-ordered-subsequence-of-vowels-dynamic-programming%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
