longestSubstringWithoutMoreThanNRepeatingCharacters

longestSubstringWithoutMoreThanNRepeatingCharacters.js

// Given a string, find the length of the longest substring without (more than n) repeating characters.
function longestSubstringWithoutMoreThanNRepeatingCharacters(str, n) {
  // lastSeenByCount[2]['s'] = third place we've seen 's' so far
  let lastSeenByCount = [...Array(n).keys()].map(_ => ({}));

  let currentLength = 0;
  let maxLength = 0;
  let maxLengthStart = 0;
  let startingFrom = 0;

  // if we start from a certain character, going as far as possible until
  // we run out of repetitions is advantageous
  // then we know the correct substring is either the one we're building
  // right now, or one of the recursively generated ones which we get by
  // cutting off the original string right after the first incidence of
  // the character that made us run out of repetitions
  // n = 2
  // uvwabcdaxyza... -> longest substring is either "uvwabcdaxyz", or in
  // bcdaxyza...
  // vwabcdaxyza etc don't contain solutions, because we already have a
  // longer one
  
  // cases:
  // from beginning until middle;
  // from beginning until end;
  // from middle until middle;
  // from middle until end;
  // single character string;
  // empty string;
  // repeated characters next to each other;

  for (let charIndex = 0; charIndex < str.length; ++charIndex) {

    let ch = str[charIndex];

    let outOfReps = true;

    for (let rep = 0; rep < n; ++rep) {
      if (lastSeenByCount[rep][ch] === undefined) {
        lastSeenByCount[rep][ch] = charIndex;

        outOfReps = false;

        break;
      }
    }

    if (outOfReps) {
	  
      if (currentLength > maxLength) {
        maxLength = currentLength;
        
        maxLengthStart = startingFrom;
      }

      // rearrange dictionaries; this makes it O(Nn) worst case, where N
      // is the length of the string
      let firstOccurrenceOfCh = lastSeenByCount[0][ch];

      for (let choppedIndex = startingFrom; choppedIndex <= firstOccurrenceOfCh; ++choppedIndex) {
        for (let dictIndex = 0; dictIndex < n; ++dictIndex) {
          if (dictIndex == n - 1 || lastSeenByCount[dictIndex + 1][str[choppedIndex]] === undefined) {
             delete lastSeenByCount[dictIndex][str[choppedIndex]];
          } else {
             lastSeenByCount[dictIndex][str[choppedIndex]] = lastSeenByCount[dictIndex+1][str[choppedIndex]];
          }
        }
      }

      lastSeenByCount[n - 1][ch] = charIndex;
	  
      let choppedOffChars = (firstOccurrenceOfCh - startingFrom) + 1;
      currentLength -= choppedOffChars;
      startingFrom = firstOccurrenceOfCh + 1;
      // console.log(
      //   str.slice(0, charIndex) + "*" + str[charIndex] + "*" + str.slice(charIndex + 1),
      //   str.slice(0, startingFrom) + "*" + str[startingFrom] + "*" + str.slice(startingFrom + 1));
    }

    currentLength += 1;
	
  }


  if (currentLength > maxLength) {
    maxLength = currentLength;
    
    maxLengthStart = startingFrom;
  }

  return str.substr(maxLengthStart, maxLength);

}

(function() {
  console.clear();

  let testStrs = [
    "uvwabcdaxyzaqwerty",
    "uvwuvwabcdaxyzaqwerty",
    "longestSubstringWithoutMoreThanNRepeatingCharacters",
    "cxyjnobglspudycwmcjjkdgrghuvzwujvhnvthegfeawbfherwhdipyyrhdgufgpxfzwkgdfycefdjqbzpddoqbgioemexmzxkzvfltlscefltvhqcgebdbgetnwcrabqeiskuvowsklmvupswvbriytjsrmyxibbdphkdxwhsijtpuiyxefwzjifojsciqzjikjgnfpzyuzaoatxjobscfcthbwtftycizkflclspgxekiroqutuoghdhpzlivufvxrppomgdjdwiyiykidkzencsgyvczjtmrinqbybimqfckvjgabasjgrjowjqqedzkkqpviikbbmohahlopcxibclrdceplsimfraetlstqqitdcopxbabgrihfyrfdupjdbbihhvdkesluroboprkrhgoisyvumpvazqbafiqfxqbyxnojproderwumzoizixpwkvambihbfuqfqlfjlfubsvhuhngthfotlcnsowojgbzwfpwoizoddoeongfncnuzgxtoxnvpqluqvkosrslhrkpxxyehrbhthaqiviqvdynrtoscrnwjcmhvhvqyinxpebivtgwibqdsxydjfbqefxqvsvazsrmqbymsfxjkrnilipyishthxtkhkncygwqjenrzmkdisgmrofmdwrhkyfthneisukeuxyhuxzwhdkoqgssfazbooflzuklhcknibsuqxsgxvzhnqcavldsvipgsniannofsxgooyciitdtoyxirjpvzsrzmmbcorsjguoqknlxjukcfwruqaidytfafhccwatqaumtjgyeysmeipuquhloiplnpoldliaibtckjxkkceffgbrpmmhoofikizevvutprddpnjgxxbmekfgnwvqybmuvlrcjsophlqodxccdfkqmteadtqzzeuoeihdvhxfjmesuqcptsntqvhchqyqbppdqbjuqygwiehaolgmqbfgrbxjbewfigduwbcshhzumqkmo"
  ];

  for (let testStr of testStrs) {
    console.log(testStr.slice(0, 100), "=>", longestSubstringWithoutMoreThanNRepeatingCharacters(testStr, 2));
  }
}());