타입 챌린지 9286 - FirstUniqueCharIndex

문제 링크

문제

문자열 s를 받고, 거기서 첫 번째로 반복되지 않는 문자를 찾은 후, 그 인덱스를 반환하라.
만약 존재하지 않는다면 -1를 반환한다.

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

내 풀이

type CharInclude<T extends string,U extends string>=
  T extends `${infer First}${infer Rest}`?
    First extends U?true:CharInclude<Rest,U>
  :false

type FirstUniqueCharIndexImplement<T extends string, Index extends any[]=[],Used extends string=never>=
  T extends `${infer First}${infer Rest}`?
    First extends Used?FirstUniqueCharIndexImplement<Rest,[...Index,1],Used>
      :CharInclude<Rest,First> extends true?FirstUniqueCharIndexImplement<Rest,[...Index,1],Used|First>
    :Index['length']
  :-1

type FirstUniqueCharIndex<T extends string> = FirstUniqueCharIndexImplement<T>

우선 사용처에서 구현용 제네릭을 사용하지 못하게 하기 위해 구현과 실제 타입을 분리했다.
CharInclude를 구현해, 특정 문자열에 해당 문자가 들어가있는지 확인할 수 있도록 하였다.

FirstUniqueCharIndexImplement는 다음과 같은 방식으로 재귀적으로 구현된다.
1) 문자열이 비어있다면 -1를 반환한다.
2) 문자열의 첫 문자가 기존 재귀에 사용되어졌다면, 그 뒤의 문자열을 재귀적으로 넣어준다. 이때, Index를 1 높여 업데이트 한다.
3) 문자열의 첫 문자가 기존 재귀에 사용되어지지 않았다면,

• Rest에 First가 들어가있지 않다면 Index를 반환한다.
• Rest에 First가 들어가있다면 Rest를 재귀에 넣어 사용했다. 이때, Index를 1 높이고, First를 Used에 넣는다.

다른 사람의 풀이

type FirstUniqueCharIndex<
  T extends string,
  _Acc extends string[] = []
> = T extends ''
  ? -1
  : T extends `${infer Head}${infer Rest}`
  ? Head extends _Acc[number]
    ? FirstUniqueCharIndex<Rest, [..._Acc, Head]>
    : Rest extends `${string}${Head}${string}`
    ? FirstUniqueCharIndex<Rest, [..._Acc, Head]>
    : _Acc['length']
  : never

풀이

다음과 같은 방식으로 구현했다.

1) 문자열이 비어있다면 -1를 반환한다.
2) 만약 첫 문자가 사용되었다면(_Acc[number]), 재귀적으로 남은 문자를 재귀적으로 사용한다. 이때, 사용된 문자에 첫 문자를 넣는다.
3) 만약 첫 문자가 사용되지 않았다면

• 나머지 뒷 문자에 Head가 포함되었다면 2)를 반복한다.
• 그렇지 않는다면, _Acc의 길이를 반환한다.

로직은 내 로직과 비슷하지만, 내 풀이에 있는 Index를 _Acc의 길이로 ,CharInclude를 Head extends _Acc[number]로 구현한 점이 인상깊었다.

참고자료

https://github.com/type-challenges/type-challenges/issues/20488