Given a string, find the repeated character present first in the string.
(Not the first repeated character, found here.)
Examples:
Input : neveropen Output : g (mind that it will be g, not e.)
Asked in: Goldman Sachs internship
Simple Solution using O(N^2) complexity: The solution is to loop through the string for each character and search for the same in the rest of the string. This would need two loops and thus not optimal.
Implementation:
C++
// C++ program to find the first // character that is repeated#include <bits/stdc++.h>#include <string.h>using namespace std;int findRepeatFirstN2(char* s){ // this is O(N^2) method int p = -1, i, j; for (i = 0; i < strlen(s); i++) { for (j = i + 1; j < strlen(s); j++) { if (s[i] == s[j]) { p = i; break; } } if (p != -1) break; } return p;}// Driver codeint main(){ char str[] = "neveropen"; int pos = findRepeatFirstN2(str); if (pos == -1) cout << "Not found"; else cout << str[pos]; return 0;}// This code is contributed // by Akanksha Rai |
C
// C program to find the first character that // is repeated#include <stdio.h>#include <string.h>int findRepeatFirstN2(char* s){ // this is O(N^2) method int p = -1, i, j; for (i = 0; i < strlen(s); i++) { for (j = i + 1; j < strlen(s); j++) { if (s[i] == s[j]) { p = i; break; } } if (p != -1) break; } return p;}// Driver codeint main(){ char str[] = "neveropen"; int pos = findRepeatFirstN2(str); if (pos == -1) printf("Not found"); else printf("%c", str[pos]); return 0;} |
Java
// Java program to find the first character// that is repeatedimport java.io.*;import java.util.*;class GFG { static int findRepeatFirstN2(String s) { // this is O(N^2) method int p = -1, i, j; for (i = 0; i < s.length(); i++) { for (j = i + 1; j < s.length(); j++) { if (s.charAt(i) == s.charAt(j)) { p = i; break; } } if (p != -1) break; } return p; } // Driver code static public void main (String[] args) { String str = "neveropen"; int pos = findRepeatFirstN2(str); if (pos == -1) System.out.println("Not found"); else System.out.println( str.charAt(pos)); }}// This code is contributed by anuj_67. |
Python3
# Python3 program to find the first # character that is repeateddef findRepeatFirstN2(s): # this is O(N^2) method p = -1 for i in range(len(s)): for j in range (i + 1, len(s)): if (s[i] == s[j]): p = i break if (p != -1): break return p# Driver codeif __name__ == "__main__": str = "neveropen" pos = findRepeatFirstN2(str) if (pos == -1): print ("Not found") else: print (str[pos]) # This code is contributed # by ChitraNayal |
C#
// C# program to find the first character// that is repeatedusing System;class GFG { static int findRepeatFirstN2(string s) { // this is O(N^2) method int p = -1, i, j; for (i = 0; i < s.Length; i++) { for (j = i + 1; j < s.Length; j++) { if (s[i] == s[j]) { p = i; break; } } if (p != -1) break; } return p; } // Driver code static public void Main () { string str = "neveropen"; int pos = findRepeatFirstN2(str); if (pos == -1) Console.WriteLine("Not found"); else Console.WriteLine( str[pos]); }}// This code is contributed by anuj_67. |
PHP
<?php// PHP program to find the first // character that is repeated function findRepeatFirstN2($s) { // this is O(N^2) method $p = -1; for ($i = 0; $i < strlen($s); $i++) { for ($j = ($i + 1); $j < strlen($s); $j++) { if ($s[$i] == $s[$j]) { $p = $i; break; } } if ($p != -1) break; } return $p; } // Driver code $str = "neveropen"; $pos = findRepeatFirstN2($str); if ($pos == -1) echo ("Not found"); else echo ($str[$pos]); // This code is contributed by jit_t?> |
Javascript
<script>// Javascript program to find the first// character that is repeatedfunction findRepeatFirstN2(s){ // This is O(N^2) method let p = -1, i, j; for(i = 0; i < s.length; i++) { for(j = i + 1; j < s.length; j++) { if (s[i] == s[j]) { p = i; break; } } if (p != -1) break; } return p;}// Driver codelet str = "neveropen";let pos = findRepeatFirstN2(str);if (pos == -1) document.write("Not found");else document.write(str[pos]); // This code is contributed by suresh07 </script> |
Output
g
Space complexity :- O(1)
Optimization by counting occurrences
This solution is optimized by using the following techniques:
- We loop through the string and hash the characters using ASCII codes. Store 1 if found and store 2 if found again. Also, store the position of the letter first found in.
- We run a loop on the hash array and now we find the minimum position of any character repeated.
Implementation:
C++
// C++ program to find the first character that // is repeated#include<bits/stdc++.h>using namespace std;// 256 is taken just to ensure nothing is left,// actual max ASCII limit is 128#define MAX_CHAR 256int findRepeatFirst(char* s){ // this is optimized method int p = -1, i, k; // initialized counts of occurrences of // elements as zero int hash[MAX_CHAR] = { 0 }; // initialized positions int pos[MAX_CHAR]; for (i = 0; i < strlen(s); i++) { k = (int)s[i]; if (hash[k] == 0) { hash[k]++; pos[k] = i; } else if (hash[k] == 1) hash[k]++; } for (i = 0; i < MAX_CHAR; i++) { if (hash[i] == 2) { if (p == -1) // base case p = pos[i]; else if (p > pos[i]) p = pos[i]; } } return p;}// Driver codeint main(){ char str[] = "neveropen"; int pos = findRepeatFirst(str); if (pos == -1) cout << "Not found"; else cout << str[pos]; return 0;}// This code is contributed // by Akanksha Rai |
C
// C program to find the first character that // is repeated#include <stdio.h>#include <string.h>// 256 is taken just to ensure nothing is left,// actual max ASCII limit is 128#define MAX_CHAR 256int findRepeatFirst(char* s){ // this is optimized method int p = -1, i, k; // initialized counts of occurrences of // elements as zero int hash[MAX_CHAR] = { 0 }; // initialized positions int pos[MAX_CHAR]; for (i = 0; i < strlen(s); i++) { k = (int)s[i]; if (hash[k] == 0) { hash[k]++; pos[k] = i; } else if (hash[k] == 1) hash[k]++; } for (i = 0; i < MAX_CHAR; i++) { if (hash[i] == 2) { if (p == -1) // base case p = pos[i]; else if (p > pos[i]) p = pos[i]; } } return p;}// Driver codeint main(){ char str[] = "neveropen"; int pos = findRepeatFirst(str); if (pos == -1) printf("Not found"); else printf("%c", str[pos]); return 0;} |
Java
// Java Program to find the first character // that is repeatedimport java.util.*;import java.lang.*;public class GFG{ public static int findRepeatFirst(String s) { // this is optimized method int p = -1, i, k; // initialized counts of occurrences of // elements as zero int MAX_CHAR = 256; int hash[] = new int[MAX_CHAR]; // initialized positions int pos[] = new int[MAX_CHAR]; for (i = 0; i < s.length(); i++) { k = (int)s.charAt(i); if (hash[k] == 0) { hash[k]++; pos[k] = i; } else if (hash[k] == 1) hash[k]++; } for (i = 0; i < MAX_CHAR; i++) { if (hash[i] == 2) { if (p == -1) // base case p = pos[i]; else if (p > pos[i]) p = pos[i]; } } return p; }// Driver code public static void main(String[] args) { String str = "neveropen"; int pos = findRepeatFirst(str); if (pos == -1) System.out.println("Not found"); else System.out.println(str.charAt(pos)); }}// Code Contributed by Mohit Gupta_OMG |
Python3
# Python 3 program to find the first # character that is repeated# 256 is taken just to ensure nothing# is left, actual max ASCII limit is 128MAX_CHAR = 256def findRepeatFirst(s): # this is optimized method p = -1 # initialized counts of occurrences # of elements as zero hash = [0 for i in range(MAX_CHAR)] # initialized positions pos = [0 for i in range(MAX_CHAR)] for i in range(len(s)): k = ord(s[i]) if (hash[k] == 0): hash[k] += 1 pos[k] = i elif(hash[k] == 1): hash[k] += 1 for i in range(MAX_CHAR): if (hash[i] == 2): if (p == -1): # base case p = pos[i] elif(p > pos[i]): p = pos[i] return p# Driver codeif __name__ == '__main__': str = "neveropen" pos = findRepeatFirst(str); if (pos == -1): print("Not found") else: print(str[pos]) # This code is contributed by# Shashank_Sharma |
C#
// C# Program to find the first character // that is repeatedusing System;public class GFG{ public static int findRepeatFirst(string s) { // this is optimized method int p = -1, i, k; // initialized counts of occurrences of // elements as zero int MAX_CHAR = 256; int []hash = new int[MAX_CHAR]; // initialized positions int []pos = new int[MAX_CHAR]; for (i = 0; i < s.Length; i++) { k = (int)s[i]; if (hash[k] == 0) { hash[k]++; pos[k] = i; } else if (hash[k] == 1) hash[k]++; } for (i = 0; i < MAX_CHAR; i++) { if (hash[i] == 2) { if (p == -1) // base case p = pos[i]; else if (p > pos[i]) p = pos[i]; } } return p; } // Driver code public static void Main() { string str = "neveropen"; int pos = findRepeatFirst(str); if (pos == -1) Console.Write("Not found"); else Console.Write(str[pos]); }} // This code is contributed by nitin mittal. |
Javascript
<script> // Javascript Program to find the first character that is repeated function findRepeatFirst(s) { // this is optimized method let p = -1, i, k; // initialized counts of occurrences of // elements as zero let MAX_CHAR = 256; let hash = new Array(MAX_CHAR); hash.fill(0); // initialized positions let pos = new Array(MAX_CHAR); pos.fill(0); for (i = 0; i < s.length; i++) { k = s[i].charCodeAt(); if (hash[k] == 0) { hash[k]++; pos[k] = i; } else if (hash[k] == 1) hash[k]++; } for (i = 0; i < MAX_CHAR; i++) { if (hash[i] == 2) { if (p == -1) // base case p = pos[i]; else if (p > pos[i]) p = pos[i]; } } return p; } let str = "neveropen"; let pos = findRepeatFirst(str); if (pos == -1) document.write("Not found"); else document.write(str[pos]);// This code is contributed by rameshtravel07.</script> |
Output
g
Time Complexity: O(N)
Auxiliary space: O(1)
Method #3:Using Built-in Python Functions:
Approach:
- Calculate all frequencies of all characters using Counter() function.
- Traverse the string and check if any element has frequency greater than 1.
- Print the character and break the loop
Below is the implementation:
C++
#include <iostream>#include <string>#include <unordered_map>using namespace std;// Function which repeats// first repeating charactervoid printrepeated(string str){ // Calculating frequencies // using unordered_map unordered_map<char, int> freq; for (char c : str) { freq++; } // Traverse the string for (char c : str) { if (freq > 1) { cout << c << endl; break; } }}// Driver codeint main(){ string str = "neveropen"; // passing string to printrepeated function printrepeated(str); return 0;} |
Java
import java.util.HashMap;public class Main { // Function which repeats // first repeating character static void printrepeated(String str) { // Calculating frequencies // using HashMap HashMap<Character, Integer> freq = new HashMap<Character, Integer>(); for (int i = 0; i < str.length(); i++) { char c = str.charAt(i); freq.put(c, freq.getOrDefault(c, 0) + 1); } // Traverse the string for (int i = 0; i < str.length(); i++) { char c = str.charAt(i); if (freq.get(c) > 1) { System.out.println(c); break; } } } // Driver code public static void main(String[] args) { String str = "neveropen"; printrepeated(str); }} |
Python3
# Python implementationfrom collections import Counter# Function which repeats # first repeating characterdef printrepeated(string): # Calculating frequencies # using Counter function freq = Counter(string) # Traverse the string for i in string: if(freq[i] > 1): print(i) break# Driver codestring = "neveropen"# passing string to printrepeated functionprintrepeated(string)# this code is contributed by vikkycirus |
C#
using System;using System.Collections.Generic;class Program { // Function which repeats // first repeating character static void PrintRepeated(string str) { // Calculating frequencies // using Dictionary Dictionary<char, int> freq = new Dictionary<char, int>(); foreach(char c in str) { if (freq.ContainsKey(c)) { freq++; } else { freq = 1; } } // Traverse the string foreach(char c in str) { if (freq > 1) { Console.WriteLine(c); break; } } } // Driver code static void Main() { string str = "neveropen"; // passing string to PrintRepeated function PrintRepeated(str); Console.ReadLine(); }}// This code is contributed by user_dtewbxkn77n |
Javascript
// JavaScript implementation// Function which repeats // first repeating characterfunction printrepeated(string) { // Calculating frequencies // using an object to store character counts let freq = {}; for (let i = 0; i < string.length; i++) { if (string[i] in freq) { freq[string[i]] += 1; } else { freq[string[i]] = 1; } } // Traverse the string for (let i = 0; i < string.length; i++) { if (freq[string[i]] > 1) { console.log(string[i]); break; } }}// Driver codelet string = "neveropen";// passing string to printrepeated functionprintrepeated(string);// this code is contributed by princekumaras |
Output
g
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #4: Solving just by single traversal of the given string.
Algorithm :
- Traverse the string from left to right.
- If current character is not present in hash map, Then push this character along with its Index.
- If the current character is already present in hash map, Then get the index of current character ( from hash map ) and compare it with the index of the previously found repeating character.
- If the current index is smaller, then update the index.
C++
#include <iostream>#include<unordered_map>#define INT_MAX 2147483647using namespace std;// Function to find left most repeating character.char firstRep (string s) { unordered_map<char,int> map; char c='#'; int index=INT_MAX; // single traversal of string. for(int i=0;i<s.size();i++) { char p=s[i]; if(map.find(p)==map.end())map.insert({p,i}); else { if(map[p]<index) { index=map[p]; c=p; } } } return c; }// Main function.int main() { // Input string. string s="abccdbd"; cout<<firstRep(s)<<endl; return 0;}// This code is contributed// by rohan007 |
Java
// Java code to find the first repeating character in a// stringimport java.util.*;public class GFG { public static int INT_MAX = 2147483647; // Function to find left most repeating character. public static char firstRep(String s) { HashMap<Character, Integer> map = new HashMap<Character, Integer>(); char c = '#'; int index = INT_MAX; // single traversal of string. for (int i = 0; i < s.length(); i++) { char p = s.charAt(i); if (!map.containsKey(p)) { map.put(p, i); } else { if (map.get(p) < index) { index = map.get(p); c = p; } } } return c; } // Main function. public static void main(String[] args) { // Input string. String s = "abccdbd"; System.out.print(firstRep(s)); System.out.print("\n"); }}// This code is contributed by Aarti_Rathi |
Python3
# Python3 code to find the first repeating character in a# stringINT_MAX = 2147483647# Function to find left most repeating character.def firstRep(s): map = dict() c = '#' index = INT_MAX # single traversal of string. i = 0 while (i < len(s)): p = s[i] if (not (p in map.keys())): map[p] = i else: if (map.get(p) < index): index = map.get(p) c = p i += 1 return cif __name__ == "__main__": # Input string. s = "abccdbd" print(firstRep(s), end="") print("\n", end="")# This code is contributed by Aarti_Rathi |
C#
// C# code to find the first repeating character in a stringusing System;using System.Collections.Generic;public static class GFG { static int INT_MAX = 2147483647; // Function to find left most repeating character. public static char firstRep(string s) { Dictionary<char, int> map = new Dictionary<char, int>(); char c = '#'; int index = INT_MAX; // single traversal of string. for (int i = 0; i < s.Length; i++) { char p = s[i]; if (!map.ContainsKey(p)) { map[p] = i; } else { if (map[p] < index) { index = map[p]; c = p; } } } return c; } // Main function. public static void Main() { // Input string. string s = "abccdbd"; Console.Write(firstRep(s)); Console.Write("\n"); }}// This code is contributed by Aarti_Rathi |
Javascript
<script>// JavaScript code to find the first repeating character in a stringconst INT_MAX = 2147483647// Function to find left most repeating character.function firstRep(s){ map = new Map(); let c = '#'; let index=INT_MAX; // single traversal of string. for(let i = 0; i < s.length; i++) { let p = s[i]; if(!map.has(p))map.set(p,i); else { if(map.get(p) < index) { index = map.get(p); c = p; } } } return c;}// Driver code// Input string.const s="abccdbd";document.write(firstRep(s)); // This code is contributed by shinjanpatra</script> |
Output
b
Time complexity: O(N)
Auxiliary Space: O(1), as there will be a constant number of characters present in the string.
More optimized Solution Repeated Character Whose First Appearance is Leftmost
This article is contributed by Suprotik Dey. If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.za or mail your article to review-team@neveropen.co.za. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
