type Includes<T extends readonly any[], U> =
  T extends [infer F, ...infer R]
  ? Equal<F, U> extends true
  ? true
  : Includes<R, U>
  : false

type Split<S extends string, Sep extends string, Acc extends string[] = []> = string extends S ? string[] : S extends "" ? []
  : Sep extends ""
  ? S extends `${infer L}${infer R}`
  ? Split<R, Sep, [...Acc, L]>
  : Acc
  : S extends `${infer L}${Sep}${infer R}`
  ? Split<R, Sep, [...Acc, L]>
  : [...Acc, S]

type Find<T extends [string, string | true][], K extends string, Res extends (string | true)[] = []> =
  T extends [infer E extends [string, string | true], ...infer R extends [string, string | true][]]
  ? E[0] extends K
    ? Includes<Res, E[1]> extends true
      ? Find<R, K, Res>
    :Find<R, K, [...Res, E[1]]>
  : Find<R, K, Res>
  : Res

// ['k1=v1','k2=v1','k2=v2','k3'] => [['k1','v1'],['k2','v1'],['k2','v2'],['k3',true]]
type Parse<T extends string[], Res extends [string, string | true][] = []> =
  T extends [infer E extends string, ...infer R extends string[]]
  ? E extends `${infer K}=${infer V}`
  ? Parse<R, [...Res, [K, V]]>
  : Parse<R, [...Res, [E, true]]>
  : Res

// [['k1','v1'],['k2','v1'],['k2','v2'],['k3',true]] => {k1:['v1']; k2:['v1','v2']; k3:[true]}
type Tokenize<T extends [string, string | true][]> = { [P in T[number][0]]: Find<T, P> }

// {k1:['v1']; k2:['v1','v2']; k3:[true]} => {k1:'v1'; k2:['v1','v2']; k3:true}
type Struct<T extends { [P in string]: (string | true)[] }> = { [P in keyof T]:
  T[P] extends (string | true)[]
    ? T[P]["length"] extends 1
      ? T[P][0]
    : T[P]
  : null
}

type ParseQueryString<S extends string> = Struct<Tokenize<Parse<Split<S, '&'>>>>

import type { Equal, Expect } from '@type-challenges/utils'

type cases = [
  Expect<Equal<ParseQueryString<''>, {}>>,
  Expect<Equal<ParseQueryString<'k1'>, { k1: true }>>,
  Expect<Equal<ParseQueryString<'k1&k1'>, { k1: true }>>,
  Expect<Equal<ParseQueryString<'k1&k2'>, { k1: true; k2: true }>>,
  Expect<Equal<ParseQueryString<'k1=v1'>, { k1: 'v1' }>>,
  Expect<Equal<ParseQueryString<'k1=v1&k1=v2'>, { k1: ['v1', 'v2'] }>>,
  Expect<Equal<ParseQueryString<'k1=v1&k2=v2'>, { k1: 'v1'; k2: 'v2' }>>,
  Expect<Equal<ParseQueryString<'k1=v1&k2=v2&k1=v2'>, { k1: ['v1', 'v2']; k2: 'v2' }>>,
  Expect<Equal<ParseQueryString<'k1=v1&k2'>, { k1: 'v1'; k2: true }>>,
  Expect<Equal<ParseQueryString<'k1=v1&k1=v1'>, { k1: 'v1' }>>,
]