Last active
June 9, 2018 22:30
-
-
Save wizo06/57454a90fe0a3f981ce7fb596853789c to your computer and use it in GitHub Desktop.
To run: "node getLongestSubstring.js <string>". Get longest substring in alphabetical order from a string. Javascript-specific methods were avoided as much as possible. Complexity is O(n).
This file contains hidden or 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
/* | |
* Assume s is a string of lower case characters. | |
* | |
* Write a program that prints the longest substring of s | |
* in which the letters occur in alphabetical order. | |
* | |
* For example, if s = 'azcbobobegghakl', then your program should print | |
* "Longest substring in alphabetical order is: beggh" | |
* | |
* In the case of ties, print the first substring. | |
* For example, if s = 'abcbcd', then your program should print | |
* "Longest substring in alphabetical order is: abc" | |
*/ | |
/* Just a switch() statement. */ | |
function charToNum(char) { | |
switch(char){ | |
case 'a': | |
return 1; | |
break; | |
case 'b': | |
return 2; | |
break; | |
case 'c': | |
return 3; | |
break; | |
case 'd': | |
return 4; | |
break; | |
case 'e': | |
return 5; | |
break; | |
case 'f': | |
return 6; | |
break; | |
case 'g': | |
return 7; | |
break; | |
case 'h': | |
return 8; | |
break; | |
case 'i': | |
return 9; | |
break; | |
case 'j': | |
return 10; | |
break; | |
case 'k': | |
return 11; | |
break; | |
case 'l': | |
return 12; | |
break; | |
case 'm': | |
return 13; | |
break; | |
case 'n': | |
return 14; | |
break; | |
case 'o': | |
return 15; | |
break; | |
case 'p': | |
return 16; | |
break; | |
case 'q': | |
return 17; | |
break; | |
case 'r': | |
return 18; | |
break; | |
case 's': | |
return 19; | |
break; | |
case 't': | |
return 20; | |
break; | |
case 'u': | |
return 21; | |
break; | |
case 'v': | |
return 22; | |
break; | |
case 'w': | |
return 23; | |
break; | |
case 'x': | |
return 24; | |
break; | |
case 'y': | |
return 25; | |
break; | |
case 'z': | |
return 26; | |
break; | |
default: | |
return 0; | |
break; | |
} | |
} | |
/* Iterates through the entire string input of length n. */ | |
function stringToNumArr(str) { | |
var tempArr = []; | |
/* Convert each character to the respective number. */ | |
for (let i = 0; i < str.length; i++) { | |
tempArr[i] = charToNum(str[i]); | |
} | |
return tempArr; | |
} | |
/* Just a switch() statement. */ | |
function NumToChar(num) { | |
switch(num){ | |
case 1: | |
return 'a'; | |
break; | |
case 2: | |
return 'b'; | |
break; | |
case 3: | |
return 'c'; | |
break; | |
case 4: | |
return 'd'; | |
break; | |
case 5: | |
return 'e'; | |
break; | |
case 6: | |
return 'f'; | |
break; | |
case 7: | |
return 'g'; | |
break; | |
case 8: | |
return 'h'; | |
break; | |
case 9: | |
return 'i'; | |
break; | |
case 10: | |
return 'j'; | |
break; | |
case 11: | |
return 'k'; | |
break; | |
case 12: | |
return 'l'; | |
break; | |
case 13: | |
return 'm'; | |
break; | |
case 14: | |
return 'n'; | |
break; | |
case 15: | |
return 'o'; | |
break; | |
case 16: | |
return 'p'; | |
break; | |
case 17: | |
return 'q'; | |
break; | |
case 18: | |
return 'r'; | |
break; | |
case 19: | |
return 's'; | |
break; | |
case 20: | |
return 't'; | |
break; | |
case 21: | |
return 'u'; | |
break; | |
case 22: | |
return 'v'; | |
break; | |
case 23: | |
return 'w'; | |
break; | |
case 24: | |
return 'x'; | |
break; | |
case 25: | |
return 'y'; | |
break; | |
case 26: | |
return 'z'; | |
break; | |
default: | |
return '_'; | |
break; | |
} | |
} | |
/* Iterates through the substring (with length no longer than n). */ | |
function NumArrToString(arr) { | |
var tempArr = []; | |
var stringified = ''; | |
/* Convert each number to the respective character. */ | |
for (let i = 0; i < arr.length; i++) { | |
tempArr[i] = NumToChar(arr[i]); | |
} | |
/* This is the equivalent of arr.join(separator) in Javascript. */ | |
for (let i = 0; i < tempArr.length; i++) { | |
stringified = stringified+tempArr[i]; | |
} | |
return stringified; | |
} | |
function getLongestSubstring(str) { | |
/* Convert the input string into an array of numbers. */ | |
var arr = stringToNumArr(str); | |
var longestSubstring = []; | |
var currentSubstring = []; | |
/* Iterates through the array of numbers to look for longest substring. */ | |
for (let i = 0; i < arr.length; i++) { | |
if(currentSubstring.length === 0) currentSubstring[i] = arr[i]; // If currentSubstring is empty, auto insert current character. | |
else{ | |
/* If current character is greater than or equal to the last character in currentSubstring, insert it. */ | |
if(arr[i] >= currentSubstring[currentSubstring.length-1]) currentSubstring[currentSubstring.length] = arr[i]; | |
else{ | |
/* If current character is less than the last character in currentSubstring, reset currentSubstring's value with current character. */ | |
if(currentSubstring.length > longestSubstring.length) longestSubstring = currentSubstring; // If currentSubstring's length is greater than longestSubstring's length, update longestSubstring. | |
currentSubstring = [arr[i]]; // This is where currentSubstring is reset. | |
} | |
} | |
} | |
return longestSubstring = NumArrToString(longestSubstring); | |
} | |
var substr = getLongestSubstring(process.argv[2]); | |
console.log(substr); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment