CODEWITHSUNDEEP
javascript
JS n00b
JS n00b

Reputation: 3

Longest substring in alphabetical order Javascript

Seeing all the people talking about longest substring in alphabetical order in Python, I have decided to try it in JS. The function should look for the longest substring inside a given string, where letters are ordered alphabetically.

Here is what I have:

var s = 'azcbobobegghakl'

function substringChecker(s) {
	var longestSub = "";
	for (var i = 0; i < s.length; i++) {
		var count = 0;
		var currSub = "";
		while((i+count)<=s.length){
			var curr = i+count;
			var next = curr+1;
			var prev = curr-1;
			if(curr !== s.length-1) {
				if(s[curr] <= s[next]){
					currSub += s[curr]
				} else {
					break;
				}
			} else {
				if(s[curr]>s[prev]) {
					currSub += s[curr];
				}
			}
		count++;
		}
		if(currSub.length >= longestSub.length) {
			longestSub = currSub;
		}
	};
	return longestSub;
}
var result = substringChecker(s);;
console.log(result);

The funny thing it works great for all test cases I can come up with, but this one. The result should be "beggh" but it is "begg" instead. Why is the h not showing up, what am I missing?

Upvotes: 0

Views: 1693

Answers (2)

Ali Alizada
Ali Alizada

Reputation: 11

first I made list of A-z then check each letter and compare it with the next letter and save it in subString and... 

function longest(str) {
  //handle the case str is just one letter
  if (str.length === 1) return str;
   // create a list of alphabet A to Z
  const alphabets = [...Array(26)].map(_ => String.fromCharCode(i++), (i = 97));
  let longString = "";
  let subSting = "";
  for (let x = 0; x < str.length; x++) {
    let char = str.charAt(x);
    const nextChar = str.charAt(x + 1);
    let charIndex = alphabets.findIndex(alphabet => alphabet === char);
    let nextCharIndex = alphabets.findIndex(alphabet => alphabet === nextChar);
    if (nextCharIndex >= charIndex) {
      subSting = subSting + nextChar;
    } else {
      if (!subSting.length) {
        subSting = subSting + char;
      }
      longString = subSting.length > longString.length ? subSting : longString;
      subSting = "";
    }
  }
  return longString;
}
console.log(longest("zyba"));

Upvotes: 0

Oriol
Oriol

Reputation: 288130

The algorithm can be linear, I think you are overcomplicating it placing loops inside loops.

I would use something like

function substringChecker(s) {
  var longestSub = "",
      length = 0,
      start = 0,
      prev = s[0];
  for (var i = 1; i <= s.length; ++i) {
    if(i == s.length || s[i] < prev) {
      if(length < i-start) {
        longestSub = s.substring(start, i);
        length = i-start;
      }
      start = i;
    }
    prev = s[i];
  };
  return longestSub;
}
document.write(substringChecker('azcbobobegghakl'));

Upvotes: 1

Related Questions