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...
c语言入门 c语言_leetcode题解03-longest-substring-without-repeating-characters
js js_leetcode题解3-longest-substring-without-repeating-characters.js
本资源"iOS-多媒体-强大的动画-序列帧和无限循环动画-9Cheetah-serial-repeating"深入探讨了这些概念,并提供了具体的实现方法。 首先,序列帧动画是一种通过连续播放一系列静态图像来创建动态效果的方法。在iOS中...
java入门 java_leetcode题解之003_Longest_Substring_Without_Repeating
在我们的示例中,我们将使用一个名为"Delete a single repeating.txt"的文本文件来描述这个过程。 首先,让我们理解单链表的基本概念。单链表是一种线性数据结构,其中每个元素(节点)包含两部分:数据和指向下一...
官方离线安装包,测试可用。使用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 ...
在压缩包`longest-substring-without-repeating-characters-master`中,可能包含了这个问题的不同实现版本,以及可能的测试用例和相关的文档。通过查看源代码和相关资料,你可以深入理解这个问题的各种解决方案,并...
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/...
标题 "A simple program that generates non repeating numbers at ran" 描述了一款简单的程序,该程序能够随机生成不重复的数字。这个程序可能被设计用于各种用途,例如抽奖系统、密码生成或者数据分析中的随机样本...
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 ...
- A.var someInts= [Int](repeating: 0, count: 3) 是正确的方式。 7. 可选链(optional chaining)的描述: - A.正确,可选链用于访问可能为nil的对象的属性、方法和子类。 - B.正确,如果目标为nil,调用不会...
ckanext-eaw_schema 要求 例如,您可能要在这里提及该扩展程序使用的CKAN版本。 安装 要安装ckanext-eaw_schema: 激活您的CKAN虚拟环境,例如: ....将ckanext-eaw_schema Python软件包安装到您的虚拟环境中: ...
导出重复数据外部模块 用户手册 该EM的最终用户文档为 它有什么作用? REDCap中对数据报告和导出的本机支持在重复表单数据时效果不佳。 以下是要考虑的报告方案: 报告中的所有数据均属于单例(非重复)形式。...