LinuxQuestions.org

LinuxQuestions.org (/questions/)
-   Programming (https://www.linuxquestions.org/questions/programming-9/)
-   -   find repeated characters in a string (https://www.linuxquestions.org/questions/programming-9/find-repeated-characters-in-a-string-141040/)

mcshen 02-01-2004 11:54 AM
find repeated characters in a string
 
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)+",");

 }
}


All times are GMT -5. The time now is 07:37 AM.