Skip to content

Instantly share code, notes, and snippets.

@wizo06
Last active June 9, 2018 22:30
Show Gist options
  • Save wizo06/57454a90fe0a3f981ce7fb596853789c to your computer and use it in GitHub Desktop.
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).
/*
* 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