Check Given String has Repeated Characters


If we want to know whether a given string has repeated characters, the simplest way is to use the existing method of finding first occurrence from the end of the string, e.g. lastIndexOf in java.  In Python, the equivalence would be rfind method of string type that will look for the last occurrence of the substring. For example, ‘3123’.rfind(‘3’) will give  value of 3.

If your characters are all ASCII characters (from 0 to 127), then maybe you can create a array that stores the first occurrence of the index, and return False if the same character (index) has been recorded before. However, the more elegant approach would be to loop each character and check if its last index of occurrence is equal to the current index. The following Python code shows the quick idea.

def hasRepeatedChars(s):
    for i in xrange(len(s)):
        if i != s.rfind(s[i]):
            return True
    return False

Most programming languages provide such methods, for example, in Java, you can use:

1
2
3
4
5
6
public static boolean hasRepeatedChars(String s) {
  for (int i = 0; i < s.length(); i ++) {
    if (i != s.lastIndexof(s.charAt(i)) return true;
  }
  return false;
}
public static boolean hasRepeatedChars(String s) {
  for (int i = 0; i < s.length(); i ++) {
    if (i != s.lastIndexof(s.charAt(i)) return true;
  }
  return false;
}

The solution has quadratic time complexity (assuming lastIndexof is linear).

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
264 words
Last Post: Easy Math Tip and LUA verification
Next Post: VBScript Customize IsBlank Function

The Permanent URL is: Check Given String has Repeated Characters

Leave a Reply