python/TangDou/JiShuanKe/2023-03-10/入门简单题.md

距离

题目描述

蒜头君最近获得了一个字符串 str，这个字符串只由小写字母构成。

蒜头君不仅是一个数学能手，英语学的更是不错，他对于 26 个英文字母非常敏感。

蒜头君发现，相同字母（如果存在）在字符串中有一个距离，比如字符串 abca，字母 a 的距离为 3（索引之差的绝对值）。

距离的定义：字符串中相对位置相邻的两个相同字母之间的距离。如果位置 i 的字母与位置 j(i < j) 的字母之间存在距离，那么需要满足 str[i] == str[j] 且 i+1 \sim j - 1 之间可以有其他字母但是不能有与 str[i] 相同的字母。

对于字符串 abcasdva，则有三个字母 a，第一个 a 和第二个 a 之间的距离为 3，第二个 a 和第三个 a 之间的距离为 4。第一个 a 和第三个 a 之间没有距离。

现在蒜头君把他的字符串给你了，你能够找到字符串字母之间的最大距离吗？

如果字符串中，所有的字母都不相同，那么最大距离为 0。

输入格式

输入共两行。

第一行输入一个正整数 n，表示字符串的长度。

第二行输入一个长度为 n 的字符串 str。

输出格式

输出共一行。

输出一个数，表示字符串字母之间的最大距离。

数据范围

对于 10\% 的数据，有 1\leq n\leq 10，且字符串中的字母互不相同。

对于另外 20\% 的数据，有 1\leq n\leq 100，且字符串中只有两种字母。

对于 100\% 的数据，有 1\leq n\leq 10^3。

题解

依次枚举每一个字母，然后寻找下一个与它相同的字母，并且维护距离的最大值。

注意，如果找到下一个与该字母相同的字母，维护后就需要通过break结束当前寻找的循环。

int ans = 0;
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (str[i] == str[j]) {
            ans = max(ans, j - i);
            break; // 注意这个 break
        }
    }
}

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    string str;
    cin >> n;
    cin >> str;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (str[i] == str[j]) {
                ans = max(ans, j - i);
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}