FirstUniqueCharIndex

Challenge

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1. (Inspired by leetcode 387)

Solution

Zur Lösung dieses Problems können wir template literal types und infer einsetzen. Bevor wir uns folgend den finalen Typ anschauen, definieren wir erstmal einen Hilfstyp, der feststellen soll, ob ein Element mehr als einmal in einer Zeichenkette auftritt. Hierzu definieren wir einen bei dem Typ IsDuplicatedChar einen Akkumulator als drittes Argument, der die Häufigkeit des Auftretens von U erfasst und zwischenspeichert. Nun extrahieren wir einfach mittels infer jeweils das erste Zeichen und prüfen, ob dieses U entspricht. Falls dies der Fall ist, erhöhen wir den Akkumulator um eins. Als Ergebnis erhalten wir true, wenn der Akkumulator eine Länge größer eins besitzt, sonst false.

type IsDuplicatedChar<
  T extends string,
  U extends string,
  OccuredAcc extends 1[] = []
> = T extends `${infer H}${infer R}`
  ? H extends U
    ? IsDuplicatedChar<R, U, [...OccuredAcc, 1]>
    : IsDuplicatedChar<R, U, OccuredAcc>
  : OccuredAcc["length"] extends 1
  ? false
  : true;

Da wir jetzt einen geeigneten Hilfstypen definiert haben, ist es jetzt einfach, den finalen Typen zu definieren. Hier durchlaufen wir ebenfalls rekursiv die Zeichenkette, und geben dann true zurück, sobald das aktuelle Zeichen nicht dupliziert ist.

type FirstUniqueCharIndex<
  T extends string,
  Original extends string = T,
  IdxAcc extends 1[] = []
> = T extends `${infer H}${infer R}`
  ? IsDuplicatedChar<Original, H> extends false
    ? IdxAcc["length"]
    : FirstUniqueCharIndex<R, Original, [...IdxAcc, 1]>
  : -1;

Challenge

Solution

References