First non-repeating char in string? in haskell or f #

Question

Given the char sequence, which is the most efficient way to find the first non-repeating char. Interested in a purely functional implementation of haskell or F #.

Answer 1

A fairly simple use Data.Setin conjunction with filterwill do the job in an efficient single-line space. Since this seems like homework, I refuse to provide the exact line in question :-)

The complexity should, I think, be O (n log m), where m is the number of different characters in the string and n is the total number of characters in the string.

Answer 2

A simple F # solution:

let f (s: string) =
  let n = Map(Seq.countBy id s)
  Seq.find (fun c -> n.[c] = 1) s

Answer 3

, O (n log n):

import List
import Data.Ord.comparing

sortPairs :: Ord a => [(a, b)]->[(a, b)]
sortPairs = sortBy (comparing fst)

index :: Integral b => [a] -> [(a, b)]
index = flip zip [1..]

dropRepeated :: Eq a => [(a, b)]->[(a, b)]
dropRepeated [] = []
dropRepeated [x] = [x]
dropRepeated (x:xs) | fst x == fst (head xs) =
                          dropRepeated $ dropWhile ((==(fst x)).fst) xs
                    | otherwise =
                          x:(dropRepeated xs)

nonRepeatedPairs :: Ord a => Integral b => [a]->[(a, b)]
nonRepeatedPairs = dropRepeated . sortPairs . index

firstNonRepeating :: Ord a => [a]->a
firstNonRepeating = fst . minimumBy (comparing snd) . nonRepeatedPairs

: , , . , .

(, [1..10000]) , - ([1..10000] ++ [1..10000] ++ [10001]) O (n ^ 2).

, , O (1), , ...

Answer 4

F # O(n log n): , , : , .

open System
open System.IO
open System.Collections.Generic

let Solve (str : string) =
    let arrStr = str.ToCharArray()
    let sorted = Array.sort arrStr
    let len = str.Length - 1

    let rec Inner i = 
        if i = len + 1 then
            '-'
        else
            let index = Array.BinarySearch(sorted, arrStr.[i])
            if index = 0 && sorted.[index+1] <> sorted.[index] then 
                arrStr.[i]
            elif index = len && sorted.[index-1] <> sorted.[index] then 
                arrStr.[i]
            elif index > 0 && index < len && 
                 sorted.[index+1] <> sorted.[index] && 
                 sorted.[index-1] <> sorted.[index] then 
                arrStr.[i]
            else
                Inner (i + 1)

    Inner 0

let _ =
    printfn "%c" (Solve "abcdefabcf")

A - , .

: - " ", , ! , .

Answer 5

Haskell O (n log n) Data.Map :

module NonRepeat (
    firstNonRepeat
    )
    where

import Data.List (minimumBy)
import Data.Map (fromListWith, toList)
import Data.Ord (comparing)

data Occurance = Occ { first :: Int, count :: Int }
    deriving (Eq, Ord)

note :: Int -> a -> (a, Occurance)
note pos a = (a, Occ pos 1)

combine :: Occurance -> Occurance -> Occurance
combine (Occ p0 c0) (Occ p1 c1) = Occ (p0 `min` p1) (c0 + c1)

firstNonRepeat :: (Ord a) => [a] -> Maybe a
firstNonRepeat = fmap fst . findMinimum . occurances
    where occurances = toList . fromListWith combine . zipWith note [0..]
          findMinimum = safeMinimum . filter ((== 1).count.snd)
          safeMinimum [] = Nothing
          safeMinimum xs = Just $ minimumBy (comparing snd) xs

Answer 6

let firstNonRepeating (str:string) =
    let rec inner i cMap =
        if i = str.Length then
            cMap 
            |> Map.filter (fun c (count, index) -> count = 1) 
            |> Map.toSeq 
            |> Seq.minBy (fun (c, (count, index)) -> index)
            |> fst      
        else
            let c = str.[i]
            let value = if cMap.ContainsKey c then 
                            let (count, index) = cMap.[c]
                            (count + 1, index)
                        else 
                            (1, i)
            let cMap = cMap.Add(c, value)
            inner (i + 1) cMap 
    inner 0 (Map.empty)

, .

let firstNonRepeating (str:string) =
    let (c, count) = str 
                     |> Seq.countBy (fun c -> c) 
                     |> Seq.minBy (fun (c, count) -> count)
    if count = 1 then Some c else None

Answer 7

- :

let firstNonRepeat s =
  let repeats = 
    ((Set.empty, Set.empty), s)
    ||> Seq.fold (fun (one,many) c -> Set.add c one, if Set.contains c one then Set.add c many else many)
    |> snd
  s
  |> Seq.tryFind (fun c -> not (Set.contains c repeats))

Answer 8

# ( , F #), , GroupBy ( ):

static char FstNonRepeatedChar(string s)
{
    return s.GroupBy(x => x).Where(xs => xs.Count() == 1).First().First();
}