Check string having unique character or not without additional data structure

Question

Here is my code without using additional data structures. Assuming all the characters are alphabetical and character checks are case-insensitive.

public static boolean isRepeated(String s) {
 if (s == null) {
 return true;
 }
 int length = s.length();
 for (int i = 0; i < length; i++) {
 if (!checkChar(i, s.toUpperCase())) {// making all character to upper case.
 return false;
 }
 }
 return true;
}
private static boolean checkChar(int i, String s) {
 char charAtI = s.charAt(i);
 //check all the character before that index;
 for (int k = 0; k < i; k++) {
 if (s.charAt(k) == charAtI)
 return false;
 }
 //check all the character after that index;
 for (int l = i + 1; l < s.length(); l++) {
 if (s.charAt(l) == charAtI)
 return false;
 }
 return true;
}

But it takes \$O(n^2)\$. Is there better way to do it, or some improvement?

To save complexity, I am using the other way, i.e. using an array.

public static boolean isRepeatedUsingArray(String s) {
 int[] charArray = new int[26];
 for(char c:s.toUpperCase().toCharArray()) {
 if(charArray[(int)c - 65] == 1) {
 return false;
 }
 charArray[(int)c - 65] = 1;
 }
 return true;
 }

Let me know your comments on this one as well.

• 200_success: What constitutes an "additional data structure"? I would consider your charArray to be a data structure.

Answer 1

1. Function name seems to be misleading. It returns true if no repeating character is found, so I find isNonRepeatedUsingArray to be more appropriate.

2. Basic input checks - when I began trying your function, I set up a few tests (included in the final code) and some of them crashed. Your code should handle at least basic input values such as null, empty string, string with spaces.

public static boolean isNonRepeatedUsingArray(String inputStr) {
 if(inputStr == null || inputStr.isEmpty())
 return false;
 String s = inputStr.replaceAll(" ", "").toUpperCase();
 // other character stripping may be put here

3. Checking for duplicates - The algorithm itself can be improved by thinking in terms of set. I am not very familiar with Java language and I have used HashMap data structure, but the bottom idea is the following:

if current element is already in the set, it is a duplicate. Else add it to the set.

This solution also has the advantage that avoids hardcoding the number of allowed characters (26).

 Map<Character, Boolean> charDict = new HashMap<Character, Boolean>();
 for (int i = 0; i < s.length(); i++) {
 Character c = s.charAt(i); 
 if (charDict.containsKey(c))
 return false;
 charDict.put(c, true);
 }

HashMap operations have a complexity of O(1), so function's overall complexity is O(n), where n is string length.

[edit] Based on Bobby's correct observation, a HashSet is a better choice (elements only, no key and values):

 HashSet<Character> charSet = new HashSet<Character>();
 for (int i = 0; i < s.length(); i++) {
 Character c = s.charAt(i); 
 if (charSet.contains(c))
 return false;
 charSet.add(c);
 }

4. Tests - it is a good habit to accompany a function with a test suite. It is particularly efficient when the code changes much (regressive testing) and helps to cover scenarios that are usually missed when developing (developers have a tendency to think in terms of making it work, not making it fail).

private static void printTestResult(String s) {
 boolean testRes = isNonRepeatedUsingArray(s);
 System.out.println("Repeating result for " + s + " is " + testRes);
}
public static void main(String []args){
 printTestResult("a");
 printTestResult("abcde");
 printTestResult("some random text");
 printTestResult("repeating");
 printTestResult(null);
}

The final code

import java.util.*;
public class HelloWorld{
 public static boolean isNonRepeatedUsingArray(String inputStr) {
 if(inputStr == null || inputStr.isEmpty())
 return false;
 String s = inputStr.replaceAll(" ", "").toUpperCase();
 Map<Character, Boolean> charDict = new HashMap<Character, Boolean>();
 for (int i = 0; i < s.length(); i++) {
 Character c = s.charAt(i); 
 if (charDict.containsKey(c))
 return false;
 charDict.put(c, true);
 }
 return true;
 }
 private static void printTestResult(String s) {
 boolean testRes = isNonRepeatedUsingArray(s);
 System.out.println("Repeating result for " + s + " is " + testRes);
 }
 public static void main(String []args){
 printTestResult("a");
 printTestResult("abcde");
 printTestResult("some random text");
 printTestResult("repeating");
 printTestResult(null);
 }
}

• Bobby: The function should be called hasOnlyUniqueCharacters(String) or hasNoRepeatingCharacters(String). The UsingArray part sounds like an implementation detail which should not matter to the user of the function and isNonRepeated raises the question "what is not repeated".
• Bobby: Also there is no need to use a Map, a Set, especially HashSet, is perfect for this and carries the meaning how it is used much better.