I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Find the First Character That Appears Once

03.21.2013
| 5394 views |
  • submit to reddit

Thursday is code puzzler day here at DZone. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Do you have code puzzlers that you'd like to share with the DZone community?  If so, please submit here. 

Find the First Character That Appears Once

Write a  method that takes a string, and returns the first character with only one occurrence in the string. For example, if the input was "this is DZone's Thursday Code Puzzler" it would return n. Have fun, and keep it efficient!

Catch up on all our previous puzzlers here.

 

Comments

Thomas Mueller replied on Thu, 2013/03/21 - 6:12am

This doesn't work well with special characters:
String s = "this is DZone's Thursday Code Puzzler".toUpperCase();
char[] x = s.toCharArray();
Arrays.sort(x);
System.out.println("" + s.replaceAll("[^" + new String(x).
    replaceAll("(.)\\1+", "") + "]", "").charAt(0)); 

Vijay Nathani replied on Thu, 2013/03/21 - 7:33am

 Using Guava library in Groovy

def giveCharacterThatOccursOnce(s) {
	def all = com.google.common.collect.HashMultiset.create(s.toLowerCase().toList())
	all.find { all.count(it) == 1 }
}
assert giveCharacterThatOccursOnce("this is DZone's Thursday Code Puzzler") in ["c","'","a","n","l","p","y"]

sun east replied on Thu, 2013/03/21 - 7:49am

 An efficient solution with O(n) time complexity:

/**
*/
def firstSingleChar(xs: String): Option[Char] = {
  val cnt = collection.mutable.Map[Char,Int]().withDefaultValue(0)
  for(x <- xs) cnt(x.toUpper) += 1
  xs.find(x => cnt(x.toUpper) == 1)
}

And a more functional style solution:

val R = """(?i)(.)(.*\1.*)""".r
def firstSingleChar(xs: String): Option[Char] = xs match {
  case "" => None
  case R(c,cs) => firstSingleChar(cs.filterNot(_.toUpper == c(0).toUpper))
  case _ => Some(xs.head)
}


Vijay Nathani replied on Thu, 2013/03/21 - 7:51am

 Pure Groovy solution

def giveCharacterThatOccursOnce(s) {
	s = s.toLowerCase();
	s.toList().find { s.count(it) == 1 }
}
assert giveCharacterThatOccursOnce("this is DZone's Thursday Code Puzzler") == "n"

Thomas Mueller replied on Thu, 2013/03/21 - 8:22am

String s = "this is DZone's Thursday Code Puzzler".toUpperCase();
for (String x = s; (x = s.replaceAll("(.)(.*)\\1(.*)", "$2$3")) != s; s = x);
System.out.println(s.substring(0, 1));

Manuel Palacio replied on Thu, 2013/03/21 - 9:47am in response to: Vijay Nathani

Nice :)

David Whatever replied on Thu, 2013/03/21 - 12:31pm

// returns nil char (0) if no unique matches found
public static char firstUniqueCharacter(String text) {
	text = text.toLowerCase();
	Map<Character, Integer> occurance = new HashMap<>();
	int length = text.length();
	for (int i = 0; i < length; i++) {
		char c = text.charAt(i);
		occurance.put(c, occurance.containsKey(c) ? null : i);
	}
	char match = 0;
	int index = Integer.MAX_VALUE;
	for (Entry<Character, Integer> entry : occurance.entrySet()) {
		if (entry.getValue() != null && index > entry.getValue()) {
			index = entry.getValue();
			match = entry.getKey();
		}
	}
	return match;
}

Carl Rischar replied on Thu, 2013/03/21 - 1:55pm

Scalaish

 def firstToAppearOnce(s: String): Option[java.lang.Character] = {
    def firstToAppear(s: String, appeared: Set[java.lang.Character]): Option[java.lang.Character] = {
      if (s.isEmpty()) return None
      val c = s.head
      val t = s.tail
      if (!appeared.contains(c) && t.indexOf(c) == -1)
        return Some(c)
      else firstToAppear(t, appeared + c )
    }
    firstToAppear(s.toLowerCase(), Set[java.lang.Character]())
  }

Ramesh Kapa replied on Thu, 2013/03/21 - 3:09pm

Here is the Dart way of finding

void main() {
	String charString = "this is DZone's Thursday Code Puzzler";
	var character = getFirstNonRepeatingCharacter(charString);
	print('First non repeating character in the string "${charString}" is: "$character"');
}

String getFirstNonRepeatingCharacter(String charString) {
	var lowerString = charString.toLowerCase();
	var length = lowerString.length;
	
	for(int i = 0; i < length; i++) {
		var character = lowerString[i];
		var replacedString = lowerString.replaceFirst(character, "");
		
		if(!replacedString.contains(character)) {
			return character;
		}
	}

}

Ulrich Cech replied on Thu, 2013/03/21 - 5:11pm

    /**
     * Returns the first character of a string, which only occurs once in the
     * whole string or 0, if no such character is found.
     * 
     * @param string the string to be processed
     * @return the character, which only occurs once or 0, 
     *         if all characters occur multiple times.
     */
    public char getFirstSingleOccurrenceCharacter(String string) {
        final String replacer = "" + (char)0;
        string = string.toLowerCase();
        for (int i = 0; i < string.length(); i++) {
            char ch = string.charAt(i);
            if (string.indexOf(ch, i+1) == -1){
                return ch;
            } else {
                string = string.replaceAll(""+ch, replacer);
            }
        }
        return 0;
    }

 Testcase:

    @Test
    public void test() {
        Assert.assertEquals('n', getFirstSingleOccurrenceCharacter(
                "this is DZone's Thursday Code Puzzler"));
        Assert.assertEquals(0, getFirstSingleOccurrenceCharacter("aabbccdd"));
    }

Alex Oscherov replied on Sat, 2013/03/23 - 6:49pm

 From the Haskell beginner:

justOneTime'::String->String->Maybe Char
justOneTime' [] _ = Nothing
justOneTime' (x:xs) y
  | x `elem` y = justOneTime' xs y
  | x `elem` xs = justOneTime' xs (x:y)
  | otherwise = Just(x)
justOneTime x = justOneTime' (map toUpper x) []

Gabor Kocsis replied on Wed, 2013/03/27 - 6:53am

Maybe not the most efficient, but shortest (in C#, using Linq):

char? FirstOccurence(string s)
{
	return s.ToLower()
			.ToCharArray()
			.GroupBy(c => c)
			.Where(w => w.Count() == 1)
			.Select(g => g.Key)
			.FirstOrDefault();
}

Joel Neely replied on Wed, 2013/03/27 - 7:34am

Here's a simple, procedural solution in go. It returns both the character value and position, and deals with failures (empty input strings or no unique characters) by returning a position of -1.

func firstUniqueRune(s string) (r1 rune, pos int) {
	pos = -1
	far := len(s)
	if far == 0 {
		return
	}
	where := make(map[rune]int)
	for i, r := range strings.ToLower(s) {
		if _, present := where[r]; present {
			where[r] = far
		} else {
			where[r] = i
		}
	}
	p1 := far
	for k, v := range where {
		if v < p1 {
			r1, p1 = k, v
		}
	}
	if p1 < far {
		pos = p1
	}
	return
}

Debra Bacon replied on Wed, 2013/03/27 - 9:18am

 lowstr=`echo $str| tr '[:upper:]' '[:lower:]'`
for (( i=0; i<${#lowstr}; i++ )); do
  c=${lowstr:$i:1}
  ccount=`grep -o "$c" <<<"$str" | wc -l`
  if [ $ccount -eq 1 ]; then
  echo $c
  break;
  fi
done

Paul Verdone replied on Wed, 2013/03/27 - 10:33am

 <?php

$t = strtoupper("this is DZone's Thursday Code Puzzler");
$s = strlen($t);

for($i = 0; $i < $s; $i++) {
   if (strpos(substr_replace($t,'', $i, 1), $t[$i]) == false) {
     echo $t[$i];
     $i=$s;
   }
}

?>

Dee Siegal replied on Wed, 2013/03/27 - 11:47am in response to: David Whatever

Similar solution using LinkedHashMap instead of HashMap, cutting total number of iterations by  average of 25%:

Character findFirstUniqueCharacter(String s) {
	s = s.toLowerCase();
	Map<Character, Integer> map = new LinkedHashMap<Character, Integer>();
	for (int i = 0; i < s.length(); i++) {
		Character character = s.charAt(i);
		Integer count = map.get(character);
		count = (count == null ? 1 : count + 1);
		map.put(character, count);			
	}
	for (Character charFound : map.keySet()) {
		if (map.get(charFound) == 1) {
			return charFound;
		}
	}
	return null;		
}

Lukasz Dobrzanski replied on Wed, 2013/03/27 - 12:30pm

Some python

from collections import Counter, OrderedDict


def get_first_uniqe_char(string):
    class OrderedCounter(Counter, OrderedDict):
        pass

    counter = OrderedCounter(string.lower())
    char_seen_once_generator = (\
        char for char, count in counter.items() if \
        count == 1 and char.isalpha())

    return next(char_seen_once_generator, None)

Bob Beechey replied on Wed, 2013/03/27 - 8:51pm

A concise Python solution:

def find_first_unique(instring):
    for each_char in instring:
        if instring.count(each_char)==1:
            return each_char


 

Mateusz Parzonka replied on Thu, 2013/03/28 - 5:48am

Java with complexity in O(n) using a byte array to store counts.

static Character firstNonRepChar(String s) {
	final byte[] counts = new byte[256];
	for (int i = 0; i < s.length(); i++) {
	    char c = Character.toLowerCase(s.charAt(i));
	    if (counts[c] < 2) {
		counts[c]++;
	    }
	}
	for (int i = 0; i < s.length(); i++) {
	    char c = Character.toLowerCase(s.charAt(i));
	    if (counts[c] == 1) {
		return c;
	    }
	}
	return null;
    }

Lukasz Dobrzanski replied on Thu, 2013/03/28 - 4:06am in response to: Bob Beechey

@Bob nice one <3, but O(n x n),  

find_first_unique(test_string) 
>>> "t"  # "n" expected

then

find_first_unique("Foo f") 
>>> " "  # None expected (same other non-letters?)

Daniel Zamora replied on Thu, 2013/03/28 - 5:42am

Scala

def firstSingleChar(c:String) : Char = {
  var cadena = c.toLowerCase + "*"
  var end = cadena.length - 1
  var encontrado = false
  var index = 0
  var resultado = '*'
  while (!encontrado) {
    var char = cadena(index)
    index += 1
    if (char >= 'a' && char <= 'z' && cadena.indexOf(char, index) == -1) { resultado = char
  encontrado = true
    } else cadena = cadena + char
    if (index == end) encontrado = true
  }
  resultado
}


Thomas Radman replied on Thu, 2013/04/04 - 5:20am

Windows PowerShell:

$string = ("this is DZone's Thursday Code Puzzler").toLower();
 foreach ($char in $string.ToCharArray()){
   if ($string.IndexOf($char) -eq $string.LastIndexOf($char)){ Write-Host $char ; break }
}

... or if you prefer "oneliners" ;) ...

$string = ("this is DZone's Thursday Code Puzzler").toLower(); $string.ToCharArray() | %{?{($string.IndexOf($_) -eq $string.LastIndexOf($_)); Write-Host $_ ; break}}

Bob Beechey replied on Thu, 2013/03/28 - 4:55pm

A Python equivalent of Thomas Radman's Powershell solution. I have had to add the conversion to lowercase statement to avoid the case sensitive error that plagued my earlier Python effort (thanks, @Lukasz)

 

def find_first_unique(instring):
    instring = instring.lower()
    for each_char in instring:
        if instring.find(each_char)==instring.rfind(each_char):
            return each_char

 

Tridib Samanta replied on Sat, 2013/03/30 - 2:10am in response to: Mateusz Parzonka


I like it best!

Bhaskar Das replied on Thu, 2013/04/04 - 2:49am

Here is a solution in Java.

input = input.toLowerCase();
		char[] arr = input.toCharArray();
		Set<Character> characters = new LinkedHashSet<Character>();
		for (char ch : arr) {
			if (!characters.contains(ch))
				characters.add(ch);
			else
				characters.remove(ch);
		}
		
		System.out.println(System.currentTimeMillis() - startTime);
		if (!characters.isEmpty())
			return (Character)characters.toArray()[0];
		else
			return null;

juan ma replied on Sat, 2013/04/06 - 11:01pm

In Ruby

# First character that appears only once

string = "this is DZone's Thursday Code Puzzler"
string.downcase!
hash = Hash.new(0)
string.each_char{
	|c|	hash[c] = hash[c] + 1
}
hash.each{
		|key, value|
		if value == 1
				puts "Winner: #{key}"
				break
		end
}

Nico Balestra replied on Thu, 2013/04/11 - 11:30am

In clojure (sorry.. no Clojure syntax highlighting available here :(

(defn [the-string]
(first (drop-while 
         (fn [[char num]]
            (not (= num 1))) 
       (reductions (fn[[k1 v1] [k2 v2]] 
                     (if (< v1 v2) [k1 v1] [k2 v2])) 
       (frequencies the-string)))))

Ram Sharma replied on Wed, 2013/05/15 - 12:16pm

 public static Character firstAndOnce(String str) {     
     for(Character ch : str.toLowerCase().toCharArray()) {
       if(str.toLowerCase().indexOf(ch) == str.toLowerCase().lastIndexOf(ch)) {
         return ch;               
       }
     }
     return null;
   }

Márcio Ferreira replied on Wed, 2013/05/29 - 4:22pm

private static String letraQueNaoRepete(String palavra) {
		
		for(int i = 0; i < palavra.length(); i++){
			String caracterComparador = String.valueOf(palavra.charAt(i));
			
			String parteFinal = palavra.substring((i + 1),palavra.length()-1);
			
			if( i == 0 ){
				if(!parteFinal.contains(caracterComparador)){
					return caracterComparador;
				}else{
					continue;
				}
			}else{
				String parteInicial = palavra.substring(0, i);
				if(!parteInicial.contains(caracterComparador) && !parteFinal.contains(caracterComparador)){
					return caracterComparador;
				}else{
					continue;
				}
			}
		}
		return null;
	}

 

Camilo Rivera replied on Mon, 2013/11/04 - 6:05am in response to: sun east

I think you are not counting map reads. It should result in something like n*ln(n) since you search the map for each element in the array.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.