Finding The First Non-Repeating Character in a String Using Swift

Finding the first non-repeating character in a String using Swift

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"

Finding The First Non-repeating Character algorithm Swift 4 (Looping over string only once)

You can create a dictionary to store the occurrences and use first(where:) method to return the first occurrence that happens only once:

Swift 4

func firstNotRepeatingCharacter(s: String) -> Character {
    var occurrences: [Character: Int] = [:]
    s.forEach{ occurrences[$0, default: 0] += 1 }
    return s.first{ occurrences[$0] == 1 } ?? "_"
}

Swift 3

func firstNotRepeatingCharacter(s: String) -> Character {
    var occurrences: [Character:Int] = [:]
    s.characters.forEach{ occurrences[$0] = (occurrences[$0] ?? 0) + 1}
    return s.characters.first{ occurrences[$0] == 1 } ?? "_"
}

Another option iterating the string in reversed order and using an array of 26 elements to store the characters occurrences

func firstNotRepeatingCharacter(s: String) -> Character {
    var chars = Array(repeating: 0, count: 26)
    var characters: [Character] = []
    var charIndex = 0
    var strIndex = 0
    s.characters.reversed().forEach {
        let index = Int(String($0).unicodeScalars.first!.value) - 97
        chars[index] += 1
        if chars[index] == 1 && strIndex >= charIndex {
            characters.append($0)
            charIndex = strIndex
        }
        strIndex += 1
    }
    return characters.reversed().first { chars[Int(String($0).unicodeScalars.first!.value) - 97] == 1 } ?? "_"
}

return the first non repeating character in a string in javascript

You can use the indexOf method to find the non repeating character. If you look for the character in the string, it will be the first one found, and you won't find another after it:

function firstNonRepeatedCharacter(string) {
  for (var i = 0; i < string.length; i++) {
    var c = string.charAt(i);
    if (string.indexOf(c) == i && string.indexOf(c, i + 1) == -1) {
      return c;
    }
  }
  return null;
}

Demo: http://jsfiddle.net/Guffa/Se4dD/

Ordering of Dictionary Swift

You are not looking correctly at the code. The filter is not applied to a dictionary. It is applied to the array (characters), which has a defined order. The dictionary is used only to store counts.

Eliminate repeating letters from Strings

You can achieve this in 2 steps. First, you need to get the unique characters of both Strings, then you need to compare the characters of the two Strings and only keep the ones that are not present in both.

The String extension getUniqueCharacters returns an array of the unique characters of the String it was called on (you can use this to get rid of the repeating characters of a String, such as 'e' in "sandeep").

var name1 = "sandeep"
var name2 = "warrior"

extension String{
    func getUniqueCharacters()->[Character]{
        var characterCounts = [Character:Int]()
        self.characters.forEach{ char in
            if characterCounts[char] != nil {
                characterCounts[char]! += 1
            } else {
                characterCounts[char] = 1
            }
        }
        return self.characters.filter{characterCounts[$0]! == 1}
    }
}

Then you just call above function on the concatenated Strings and you're done.

let name3 = name1+name2
let name4 = name3.getUniqueCharacters().map{String($0)}.joined()
print(name4) //sndpwio

Using Swift Get array of non repeating numbers from array of numbers

You may try the following:

let numArray = [1, 2, 3, 3, 4, 5, 5]

// Group by value
let grouped = Dictionary(grouping: numArray, by: { $0 })

// Filter by its count, convert back to Array and sort
let unique = Array(grouped.filter { $1.count == 1 }.map(\.key)).sorted()

print(unique) // [1, 2, 4]

---

Here is an alternative way without using higher order functions:

let numArray = [1, 2, 3, 3, 4, 5, 5]

// Group by value
let grouped = Dictionary(grouping: numArray, by: { $0 })

var uniqueArray = [Int]()

for (key, value) in grouped {
    if value.count == 1 {
        uniqueArray.append(key)
    }
}

print(uniqueArray.sorted()) // [1, 2, 4]

Finding the first Non-repeating Character in the given string, not able to pass a few test cases due to Timeout

The minimal possible time complexity for this task is linear O(n), because we need to examine every character in the given string to find out whether a particular character is unique.

Your current solution runs in O(n^2) - Collections.frequency() iterates over all characters in the string and this iteration and this method is called for every character. That's basically a brute-force implementation.

We can generate a map Map<Character,Boolean>, which associates each character with a boolean value denoting whether it's repeated or not.

That would allow to avoid iterating over the given string multiple times.

Then we need to iterate over the key-set to find the first non-repeated character. As the Map implementation LinkedHashMap is used to ensure that returned non-repeated character would be the first encountered in the given string.

To update the Map I've used Java 8 method merge(), which expects three arguments: a key, a value, and a function responsible for merging the old value and the new one.

public char solution(String s) {
    Map<Character, Boolean> isNonRepeated = getMap(s);
    
    for (Map.Entry<Character, Boolean> entry: isNonRepeated.entrySet()) {
        if (entry.getValue()) {
            return entry.getKey();
        }
    }        
    
    return '_';
}

public Map<Character, Boolean> getMap(String s) {
    Map<Character, Boolean> isNonRepeated = new LinkedHashMap<>();
    
    for (int i = 0; i < s.length(); i++) {
        isNonRepeated.merge(s.charAt(i), true, (v1, v2) -> false);
    }
    return isNonRepeated;
}

In case if you're comfortable with streams, this problem can be addressed in one statement (the algorithm remains the same and time complexity would be linear as well):

public char solution(String s) {
    
    return s.chars()
        .mapToObj(c -> (char) c)
        .collect(Collectors.toMap( // creates intermediate Map<Character, Boolean>
            Function.identity(),   // key
            c -> true,             // value - first occurrence, character is considered to be non-repeated
            (v1, v2) -> false,     // resolving values, character is proved to be a duplicate
            LinkedHashMap::new
        ))
        .entrySet().stream()
        .filter(Map.Entry::getValue)
        .findFirst()
        .map(Map.Entry::getKey)
        .orElse('_');
}

Get nth character of a string in Swift

Attention: Please see Leo Dabus' answer for a proper implementation for Swift 4 and Swift 5.

Swift 4 or later

The Substring type was introduced in Swift 4 to make substrings
faster and more efficient by sharing storage with the original string, so that's what the subscript functions should return.

Try it out here

extension StringProtocol {
    subscript(offset: Int) -> Character { self[index(startIndex, offsetBy: offset)] }
    subscript(range: Range<Int>) -> SubSequence {
        let startIndex = index(self.startIndex, offsetBy: range.lowerBound)
        return self[startIndex..<index(startIndex, offsetBy: range.count)]
    }
    subscript(range: ClosedRange<Int>) -> SubSequence {
        let startIndex = index(self.startIndex, offsetBy: range.lowerBound)
        return self[startIndex..<index(startIndex, offsetBy: range.count)]
    }
    subscript(range: PartialRangeFrom<Int>) -> SubSequence { self[index(startIndex, offsetBy: range.lowerBound)...] }
    subscript(range: PartialRangeThrough<Int>) -> SubSequence { self[...index(startIndex, offsetBy: range.upperBound)] }
    subscript(range: PartialRangeUpTo<Int>) -> SubSequence { self[..<index(startIndex, offsetBy: range.upperBound)] }
}

To convert the Substring into a String, you can simply
do String(string[0..2]), but you should only do that if
you plan to keep the substring around. Otherwise, it's more
efficient to keep it a Substring.

It would be great if someone could figure out a good way to merge
these two extensions into one. I tried extending StringProtocol
without success, because the index method does not exist there. Note: This answer has been already edited, it is properly implemented and now works for substrings as well. Just make sure to use a valid range to avoid crashing when subscripting your StringProtocol type. For subscripting with a range that won't crash with out of range values you can use this implementation

---

Why is this not built-in?

The error message says "see the documentation comment for discussion". Apple provides the following explanation in the file UnavailableStringAPIs.swift:

Subscripting strings with integers is not available.

The concept of "the ith character in a string" has
different interpretations in different libraries and system
components. The correct interpretation should be selected
according to the use case and the APIs involved, so String
cannot be subscripted with an integer.

Swift provides several different ways to access the character
data stored inside strings.

• String.utf8 is a collection of UTF-8 code units in the
  string. Use this API when converting the string to UTF-8.
  Most POSIX APIs process strings in terms of UTF-8 code units.

• String.utf16 is a collection of UTF-16 code units in
  string. Most Cocoa and Cocoa touch APIs process strings in
  terms of UTF-16 code units. For example, instances of
  NSRange used with NSAttributedString and
  NSRegularExpression store substring offsets and lengths in
  terms of UTF-16 code units.

• String.unicodeScalars is a collection of Unicode scalars.
  Use this API when you are performing low-level manipulation
  of character data.

• String.characters is a collection of extended grapheme
  clusters, which are an approximation of user-perceived
  characters.

Note that when processing strings that contain human-readable text,
character-by-character processing should be avoided to the largest extent
possible. Use high-level locale-sensitive Unicode algorithms instead, for example,
String.localizedStandardCompare(),
String.localizedLowercaseString,
String.localizedStandardRangeOfString() etc.

How to go through the elements of type string

You can try:

func countDuplicates(_ s:String) -> Int {
    return s.count - Set(s).count
}

Where:

s.count // total number of characters
Set(s).count // number of unique characters

---

Related Topics