问题描述

下面是有关这个问题的描述部分。

英文

Given a string s, return the first non-repeating character in it and return its index. If it does not exist, return -1.

中文

针对给定的一个字符串 s，你需要写一个算法，返回给定字符串中不重复字符。

这个题目在随后的面试中又出来变种。

这次需要函数返回的找到的字符串，同时输入的字符串中还有大小写。

另外，因为在线编译器的限制，你又不能使用 HashMap。

 

解题思路

使用 Java 来说还是相对比较好处理的。

解题思路也比较简单，你需要使用一个中间变量来存储，首先还是需要将进行处理的字符串转换为 char 的数组。

然后在数组中拿到第一个字符。

当你拿到第一个字符的时候，你做这样一件事情，将这个字符对目标字符串进行替换为 “”;

如果有相同的，那么肯定会被替换掉，同时你再考虑替换掉一次大写的，一次小写的。

如果有大写字母相同的，那么也会被替换掉。

例如字符串 “serTSSEr”，那么你在完成后上面的算法后，假设我们对比第一个要替换的字符是 s，那么完成后算法后的字符串为 “erTEr”。

我们发现字符串的长度就不是原始长度 -1 了，因为你替换了多个字符串，因此可以知道这个被查找的字符是重复的。

当我们循环到字符 T 的时候，我们会发现完成后算法后的字符串长度就是原始输入字符串长度 -1，那么我们就知道 T 就是我们需要输出的字符了。

需要注意的是特殊情况 “ssee” 这种情况，如果你循环到最后，可能会发现原始字符的长度和完成整个循环后字符的长度没有变化，那么说明所有的字符都有重复，那么你应该返回 “”。

更进一步

为了减少搜索次数，你可以在完成后第一次替换后的余下的字符串中进行算法查找和替换，因为这个算法值需要找到字符，并不需要你输出下标。

因此在循环中，下次需要查找的字符串长度就减少了，算法的效率也就更高了。

完整测试代码，请参考题目中的 GitHub 链接地址：https://github.com/cwiki-us-docs/java-tutorials/blob/master/toolkits/codebank/src/test/java/com/ossez/toolkits/codebank/tests/leetcode/LeetCode0387FirstUniqueCharacterTest.java

我们这里将这个测试方法写在下面供需要的童鞋参考。

/**
 * Return the first Uniq Char String without using Map
 * @param data
 * @return
 */
private String firstUniqCharString(String data) {
    // NULL CHECK
    if (data.equals("")) {
        return "";
    }

    char[] strArray = data.toCharArray();
    String retStr = "";

    if (data.length() == 1) {
        retStr = data;
    }

    for (int i = 0; i < strArray.length; i++) {
        String valStr = Character.toString(strArray[i]);
        String rData = data;
        rData = data.replace(valStr, "");
        rData = rData.replace(valStr.toUpperCase(Locale.ROOT), "");
        rData = rData.replace(valStr.toLowerCase(Locale.ROOT), "");

        if (rData.length() == 0) {
            retStr = "";
        } else if (rData.length() + 1 == data.length()) {
            retStr = valStr;
            break;
        }
    }
    return retStr;
}