find repeated characters in a string

mcshen · 02-01-2004, 11:54 AM

How would I go about finding the locations of the repeated character in a string(or array). say, if I have

HIMYDIFIWAI

then, it will return

1,5,7,10

jtshaw · 02-01-2004, 12:12 PM

Well, one way I might do it is to make a dynamic array of structs. The struct would contain a counter and a character. Each time I find a new character I add it to the dynamic array of structs and set the counter for it's node to 1. Each time I have a repeat I would increment the counter for the character. Course, there is probably an easier way, I don't do well thinking about coding algorithms after 2 hours of tail gate partying

david_ross · 02-01-2004, 01:35 PM

Since you never gave a language, here's one in perl

Code:

#!/usr/bin/perl

$string="HIMYDIFIWAI";

$num=0;
foreach $char (split(//,$string)){
$str=$string;
$count = $str =~ s/$char//g;
if($count>1){print $num.", "}
$num++;
}

exit;

Strike · 02-01-2004, 02:42 PM

The problem definition isn't very clear. No language specified, and is it always going to be just one character that's repeated in the string?

mcshen · 02-01-2004, 05:32 PM

not one character. maybe more than one chars that are repeated.

language: java

thx

caged · 02-02-2004, 10:21 AM

have the program loop through for each charector in the string checking if their are duplicates, skipping charAt(n) where n is the value of any char already defined as a duplicate of another.

Strike · 02-02-2004, 02:44 PM

A simpler way to do this would be to loop through the string once, keeping a mapping of the letters to their positions in the string. Then, once this is done, just check the mapping for letters with more than one position in the string. This is O(n) behavior.

jtshaw · 02-02-2004, 02:55 PM

I like Strikes idea, that was what I was trying to get at with my original post.

Strike · 02-02-2004, 04:06 PM

The python version (which is probably at least somewhat understandable to non-Pythoners who have some programming experience) would be:

Code:

s = "some string, of course"
pos_map= {}

for pos, char in enumerate(s):
    if char in pos_map:
        pos_map[char].append(pos)
    else:
        pos_map[char] = [pos]

for char, pos_list in pos_map.items():
    if len(pos_list) > 1:
        print "%r -> %r" % (char, pos_list)

For that string ("some string, of course") above, this returns:

Code:

' ' -> [4, 12, 15]
'e' -> [3, 21]
'o' -> [1, 13, 17]
's' -> [0, 5, 20]
'r' -> [7, 19]

Looking_Lost · 02-02-2004, 05:43 PM

How about this, although admittedly only tested it on two different strings

Code:

import java.util.ArrayList;

public class test
{
 public static void main(String args[])
 {

   String s1=new String("HIMDIFIWAI");
                            
   ArrayList results=new ArrayList();
    char tempChar;                        

  for(int i=0; i<s1.length(); i++)
   {
      tempChar=s1.charAt(i);

     if( s1.indexOf(tempChar)!=s1.lastIndexOf(tempChar))
       {
         results.add(new Integer(i));
        }
    }


   for(int i=0; i<results.size(); i++)
     System.out.print(results.get(i)+",");

 }
}