Home > leetcode > First Unique Character in a String (Dart)

First Unique Character in a String (Dart)


At the time we solved this kata there is no official dart version.

Today we solve a very popular 'kata' on Leetcode #387 First Unique Character in a String

Difficulty level: Easy

Related Topics: Hash Table, String

Disclaimer: You might have different results in Runtime and Memory Usage, it's okay 🤣 it how it works.


Description:

Given a string, find the first non-repeating character in it and return its index. If it doesn't exist, return -1.

Examples:

str = "leetcode"
return 0.

str = "loveleetcode"
return 2.

Note:

 You may assume the string contains only lowercase English letters.

And your playground looks like this:

int firstUniqChar(String str)  {


};

Solution 1

At first, let's solve this by using a hash table aka HashMap in Dart.

The idea is to go thru the string and store how many times a letter appears in the string.

import 'dart:collection'; // we need it for HashMap

    HashMap hashTable = new HashMap<String, int>();

    for (int i = 0; i < str.length; i++) {
    if (hashTable[str[i]] != null) {
        hashTable[str[i]] = hashTable[str[i]] + 1;
    } else {
        hashTable[str[i]] = 1;
    }
}

And our object looks like this:

{e: 3, l: 1, c: 1, d: 1, o: 1, t: 1}

Now we have to return the first unique character, but as you can see object doesn't guarantee order. That's why we have to loop over the string and find the first letter with value 1. Or return -1 if there is no unique character.

for (int i = 0; i < str.length; i++) {
    if (hashTable[str[i]] == 1) {
        return i;
    }
}

We go thru string letter by letter and check where this letter has value 1 in letterCounter if so, we return its number.

Full solution

import 'dart:collection';

int firstUniqChar(String str) {
  HashMap hashTable = new HashMap<String, int>();

  for (int i = 0; i < str.length; i++) {
    if (hashTable[str[i]] != null) {
      hashTable[str[i]] = hashTable[str[i]] + 1;
    } else {
      hashTable[str[i]] = 1;
    }
  }

  for (int i = 0; i < str.length; i++) {
    if (hashTable[str[i]] == 1) {
      return i;
    }
  }

  return -1;
}

Solution 2

Let's try a different approach.

If indexOf() equal lastIndexOf() this is a unique character. So we have to loop over the string and return first unique character.

int firstUniqChar(String str) {
  for (int i = 0; i < str.length; i++) {
    if (str.indexOf(str[i]) == str.lastIndexOf(str[i])) {
      return i;
    }
  }

  return -1;
}
© 2021, Andrew Losseff