Given a string, find the first non-repeating character in it. For example, if the input string is “GeeksforGeeks”, then output should be ‘f’ and if input string is “GeeksQuiz”, then output should be ‘G’.
We can use string characters as index and build a count array. Following is the algorithm.
1) Scan the string from left to right and construct the count array. 2) Again, scan the string from left to right and check for count of each character, if you find an element who's count is 1, return it.
Example:
Input string: str = geeksforgeeks 1: Construct character count array from the input string. .... count['e'] = 4 count['f'] = 1 count['g'] = 2 count['k'] = 2 …… 2: Get the first character who's count is 1 ('f').
Implementation:
#include<stdlib.h> #include<stdio.h> #define NO_OF_CHARS 256 /* Returns an array of size 256 containg count of characters in the passed char array */ int *getCharCountArray(char *str) { int *count = (int *)calloc(sizeof(int), NO_OF_CHARS); int i; for (i = 0; *(str+i); i++) count[*(str+i)]++; return count; } /* The function returns index of first non-repeating character in a string. If all characters are repeating then returns -1 */ int firstNonRepeating(char *str) { int *count = getCharCountArray(str); int index = -1, i; for (i = 0; *(str+i); i++) { if (count[*(str+i)] == 1) { index = i; break; } } free(count); // To avoid memory leak return index; }
Can we do it by traversing the string only once?
The above approach takes O(n) time, but in practice it can be improved. The first part of the algorithm runs through the string to construct the count array (in O(n) time). This is reasonable. But the second part about running through the string again just to find the first non-repeater is not good in practice. In real situations, your string is expected to be much larger than your alphabet. Take DNA sequences for example: they could be millions of letters long with an alphabet of just 4 letters. What happens if the non-repeater is at the end of the string? Then we would have to scan for a long time (again).
We can augment the count array by storing not just counts but also the index of the first time you encountered the character e.g. (3, 26) for ‘a’ meaning that ‘a’ got counted 3 times and the first time it was seen is at position 26. So when it comes to finding the first non-repeater, we just have to scan the count array, instead of the string. Thanks to Ben for suggesting this approach.
Following is C implementation of the extended approach that traverses the input string only once.
#include <stdlib.h> #include <stdio.h> #include <limits.h> #define NO_OF_CHARS 256 // Structure to store count of a character and index of the first // occurrence in the input string struct countIndex { int count; int index; }; /* Returns an array of above structure type. The size of array is NO_OF_CHARS */ struct countIndex *getCharCountArray(char *str) { struct countIndex *count = (struct countIndex *)calloc(sizeof(countIndex), NO_OF_CHARS); int i; for (i = 0; *(str+i); i++) { (count[*(str+i)].count)++; // If it's first occurrence, then store the index if (count[*(str+i)].count == 1) count[*(str+i)].index = i; } return count; } /* The function returns index of the first non-repeating character in a string. If all characters are repeating then reurns INT_MAX */ int firstNonRepeating(char *str) { struct countIndex *count = getCharCountArray(str); int result = INT_MAX, i; for (i = 0; i < NO_OF_CHARS; i++) { // If this character occurs only once and appears // before the current result, then update the result if (count[i].count == 1 && result > count[i].index) result = count[i].index; } free(count); // To avoid memory leak return result; }
Reference:
http://www.geeksforgeeks.org/given-a-string-find-its-first-non-repeating-character/
相关推荐
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...
iOS_多媒体_强大的动画_序列帧和无限循环动画_9Cheetah-serial-repeating
删除单链表中的重复项 并学习如何创建fun函数 - 副本
官方离线安装包,测试可用。使用rpm -ivh [rpm完整包名] 进行安装
官方离线安装包,测试可用。使用rpm -ivh [rpm完整包名] 进行安装
官方离线安装包,测试可用。使用rpm -ivh [rpm完整包名] 进行安装
Lesson 6 - Capstone project: your first Python program-convert hours to minutes UNIT 2 - STRINGS, TUPLES, AND INTERACTING WITH THE USER Lesson 7 - Introducing string objects: sequences of characters ...
Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1. s = leetcode return 0. s = loveleetcode, return 2. 二、题解 方法一:map map 对...
A simple program that generates non repeating numbers at random in certain ranges.
421 | [Maximum XOR of Two Numbers in an Array](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/) | [C++](./C++/maximum-xor-of-two-numbers-in-an-array.cpp) [Python](./Python/...
php'content' => [ 'type' => 'repeating' , 'settings' => [ 'field_groups' => [ [ 'name' => 'Heading' , 'slug' => 'heading' , 'elements' => [ [ 'label' => 'Main Heading' , 'slug' => 'main_heading' , '...
repeat ( 'A' , 5 ) ;//=> AAAAA 参量string {String} :要重复的字符串number {Number} :重复字符串的次数returns {String} :重复的字符串基准测试重复字符串比本地方法快得多(它本身比方法快): # 2xrepeat-...
Locating the first instance of a character 52 Locating the index of a character 53 Determining the class of a string 54 Locating the last instance of a string 56 Determining the size of a string 57 ...
最长子串无重复字符没有重复字符的最长子串的长度( )
ckanext-eaw_schema 要求 例如,您可能要在这里提及该扩展程序使用的CKAN版本。 安装 要安装ckanext-eaw_schema: 激活您的CKAN虚拟环境,例如: ....将ckanext-eaw_schema Python软件包安装到您的虚拟环境中: ...
导出重复数据外部模块 用户手册 该EM的最终用户文档为 它有什么作用? REDCap中对数据报告和导出的本机支持在重复表单数据时效果不佳。 以下是要考虑的报告方案: 报告中的所有数据均属于单例(非重复)形式。...
这是来自LeetCode的已解决任务的存储库使用Java语言解决任务 ...repeating-character-replacement/ MergeIntervals.java - //leetcode.com/problems/merge-intervals/ ReverseLinkedList.java - //leetcode.com/problem
$ npm install --global repeating-cli 用法 $ repeating --help Usage $ repeating <count> [string] Examples $ echo "foo$(repeating 10)bar" foo bar $ repeating 3 'unicorn ' unicorn unicorn unicorn
CSS repeating-linear-gradient 方法 创造一个可重复的渐变。它接受和普通线性渐变相同的属性值并且表现也一致。 但它会自动在延伸的方向上重复 color stops。每段起始和结束的 color stop 之间是一个基本的...