4

This finds the duplicates in the array, but i'm looking for something that finds the first non-repeating character in a string. I've been trying to figure out a way to do this and I cannot figure it out. This is the closest i've gotten.

var strArray = ["P","Q","R","S","T","P","R","A","T","B","C","P","P","P","P","P","C","P","P","J"]

println(strArray)

var filter = Dictionary<String,Int>()
var len = strArray.count
for var index = 0; index < len  ;++index {
var value = strArray[index]
if (filter[value] != nil) {
    strArray.removeAtIndex(index--)
    len--
}else{
    filter[value] = 1
}
}
println(strArray)
6
  • First non-repeating or the first repeated ? Commented Dec 7, 2014 at 0:14
  • Do You want to identify the "P"? Commented Dec 7, 2014 at 0:15
  • I want to find the first character in a string that doesn't repeat. Example: "DEFD -> E" Commented Dec 7, 2014 at 0:17
  • ok you have to create a second array and store one by one until you find a duplicate Commented Dec 7, 2014 at 0:20
  • @LeonardoSavioDabus Would that work with the above code? If so could I see an example of something you would change or could you point me in the direction to find the answer? Thanks for your help. Commented Dec 7, 2014 at 0:26

10 Answers 10

11

In order to tell if a character repeats itself, go through the entire array once, incrementing the count of occurrences in a dictionary:

let characters = ["P","Q","R","S","T","P","R","A","T","B","C","P","P","P","P","P","C","P","P","J"]

var counts: [String: Int] = [:]
for character in characters {
    counts[character] = (counts[character] ?? 0) + 1
}


let nonRepeatingCharacters = characters.filter({counts[$0] == 1})
// ["Q", "S", "A", "B", "J"]
let firstNonRepeatingCharacter = nonRepeatingCharacters.first!
// "Q"
Sign up to request clarification or add additional context in comments.

6 Comments

@mattt Would this also work well if you wanted to find a duplicate integer in an array between 1 and 1,000,000?
I will try to implement my original idea of doing a find at the array as it goes increasing and I will post it for you so you can compare the speed and pick the fastest one. But i think his solution is probably the fastest one.
@BradleyScottMaskell I don't see why not. Though, if your problem is constrained to finding duplicate integers in a specific domain, an even more elegant solution would be to create a bit mask, setting the nth bit to 1 for each number n in your array. This also has the nice benefit of having the results ordered.
@LeonardoSavioDabus There's no avoiding going through the entire array at least once, so any solution will be O(n). I would expect any speed difference between solutions with similar performance characteristics to be negligible.
what if the first non-repeating character comes at index 10 and the string is of length 1000?. It is more complex solution in such cases
|
5

Here is a simple solution

let inputString = "PQRSTPRATBCPPPPPCPPJ"

func nonRepeat (_ input: String) -> String {
    for char in input {
        if input.firstIndex(of: char) == input.lastIndex(of: char) {
            return String(char)
        }
    }
    return ""
}
print (nonRepeat(inputString))

In the above example it would print "Q"

Comments

1
func firstNonRepeatedCharacter(input: String) -> Character?{
    var characterCount : [Character : Int] = [:]
    var uniqueCharacter: Character?

    for character in input{
        if let count = characterCount[character]{
            characterCount[character] = count + 1
            if(uniqueCharacter == character)
            {
                uniqueCharacter = nil
            }
        }
        else{
            characterCount[character] = 1
            if(uniqueCharacter == nil){
                uniqueCharacter = character
            }
        }
    }
    return uniqueCharacter
}

Without extra loop to find character from characterCount dictionary

Comments

0

Here is the way I have found to detect the first non-repeated character. It removes spaces and punctuation to find the actual letter or number that does not repeat.

extension String {

func removeNonAlphaNumChars() -> String {
    let charSet = NSCharacterSet.alphanumericCharacterSet().invertedSet

    return self
        .componentsSeparatedByCharactersInSet(charSet)
        .joinWithSeparator("")
}

var firstNonRepeatedCharacter: Character? {
    let alphaNumString = self.removeNonAlphaNumChars()

    let characters = alphaNumString.characters
    let count = characters.count
    guard count > 0 else { return nil }

    // Find unique chars
    var dict: [Character: Int?] = [:]
    for (index, char) in characters.enumerate() {
        if dict[char] != nil {
            dict[char] = (nil as Int?)
        }
        else {
            dict[char] = index
        }
    }

    return dict.filter { $0.1 != nil }.sort { $0.1 < $1.1 }.first?.0
}
}

Comments

0

I totally wonder why the accepted answer was considered correct. They are using

.first

method of a dictionary and that according to documentation would return a random element in the dictionary and not the first element as a dictionary in swift is not ordered like an array. check the image to see dictionary as an unordered collection

please do find below an implementation that works

func firstNonRepeatingLetter(_ str: String)  -> String{
   var characterDict = [String : Int]()

   for character in str{
       let lower = character.lowercased()
       if let count = characterDict[lower]{
         characterDict[lower] = count + 1
       }else{
        characterDict[lower] = 1
       }
   }

   let filtered = characterDict.filter { $0.value == 1}
   for character in str{
       let lower = character.lowercased()
       if let _ = filtered[lower]{
        return lower
       }
   }

   return ""
}


firstNonRepeatingLetter("moonmen") would return "e". 

Comments

0

We can iterate once and keep the letter counts inside a dictionary. Then, iterate again and return first letter where we see it was encountered once only (or "_" if not found a non-repeating letter):

func firstNotRepeatingCharacter(s: String) -> Character {
    var letterCounts: [String: Int] = [:]
    var result: Character = "_"

    for letter in s {
        if let currentLetterCount = letterCounts[String(letter)] {
            letterCounts[String(letter)] = currentLetterCount + 1
        } else {
            letterCounts[String(letter)] = 1
        }
    }

    for letter in s {
        if letterCounts[String(letter)] == 1 {
            result = letter
            break
        }
    }

    return result
}

Comments

0

OrderedDictionary makes this easy for all Sequences of Hashables, not just Strings:

import struct OrderedCollections.OrderedDictionary

extension Sequence where Element: Hashable {
  var firstUniqueElement: Element? {
    OrderedDictionary(zip(self, true)) { _, _  in false }
      .first(where: \.value)?
      .key
  }
}
/// `zip` a sequence with a single value, instead of another sequence.
public func zip<Sequence: Swift.Sequence, Constant>(
  _ sequence: Sequence, _ constant: Constant
) -> LazyMapSequence<
  LazySequence<Sequence>.Elements,
  (LazySequence<Sequence>.Element, Constant)
> {
 sequence.lazy.map { ($0, constant) }
}

Comments

-2
func getFirstUniqueChar(string:String)->Character?{
var counts: [String: Int] = [:]
for character in string {
    let charString = "\(character)"
    counts[charString] = (counts[charString] ?? 0) + 1
}
let firstNonRepeatingCharacter = string.first {counts["\($0)"] == 1}
return firstNonRepeatingCharacter
}

print(getFirstUniqueChar(string: string))

Comments

-2
import Foundation
import Glibc
var str:String = "aacbbcee"//your input string
var temp:String = ""
var dict:[Character:Int] = [:]

for char in str{
    if let count = dict[char]{
        dict[char] = count+1//storing values in dict and incrmenting counts o key
    }
    else{
        dict[char] = 0
    }
}
var arr:[Character] = []
for (key, value) in dict{
    if value == 0{
        arr.append(key)//filtering out, take characters which has value>0
    }  //int(arr)
}//print(arr.count)
if arr.count != 0{
outer:for char in str{//outer is labeling the loop
    for i in arr{
        if i == char{
        print(i,"is first")//matching char with array elements if found break
        break outer
        }
        else{
            continue
        }
    }
}
}
else{
print("not found")
}

Comments

-2
func firstNonRepeatedChar(string: String) -> Character {
var arr: [Character] = []
var dict: [Character : Int] = [:]

for character in string.description {
    arr.append(character)
}

for character in arr {
    dict[character] = (dict[character] ?? 0) + 1
}
let nonRepeatedArray = arr.filter { char in
    if dict[char] == 1 {return true}
    return false
}
let firstNonRepeatedChar = nonRepeatedArray.first
return firstNonRepeatedChar! 
}
print(firstNonRepeatedChar(string: "strinstrig"))

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.