Skip to content

Instantly share code, notes, and snippets.

@khatv911 khatv911/max_substring.js
Last active Feb 17, 2019

Embed
What would you like to do?
find max substring
// find max substring
// using dynamic programming
// Time: O(n)
var maxSubString = s => {
if (s.length <=1) return s
let dp = [] // max-len of the substring at index i
var idx=0// mark start index of max substring
dp[0] =1
for(var i=1; i < s.length; i++){
if(s.charAt(i) > s.charAt(i-1)
&& s.substr(idx,dp[i-1]) < s.substring(i)){
dp[i]=1
idx = i
}
else dp[i] = dp[i-1]+1
}
return s.substr(idx,dp[s.length-1])
};
//test
console.log(maxSubString("abanbna")) //nbna
console.log(maxSubString("ababnan")) //nan
console.log(maxSubString("abcbabn")) //n
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.