Last active
February 17, 2019 12:30
-
-
Save khatv911/fbadeb754480a7e0481fce2b1fd60ccd to your computer and use it in GitHub Desktop.
find max substring
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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