Skip to content

Instantly share code, notes, and snippets.

@khatv911
Last active February 17, 2019 12:30
Show Gist options
  • Save khatv911/fbadeb754480a7e0481fce2b1fd60ccd to your computer and use it in GitHub Desktop.
Save khatv911/fbadeb754480a7e0481fce2b1fd60ccd to your computer and use it in GitHub Desktop.
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