Queries for Characters in a Repeated String in Java

问题陈述

给定一个字符串 X。通过多次重复字符串 X 来形成一个字符串 S，即多次将字符串 X 与自身连接。有 Q 个查询，形式为 i 和 j。任务是如果 S 中索引 i 处的元素与索引 j 处的元素相同，则显示“Yes”，否则为每个查询打印“No”。

让我们通过一个例子来理解这个问题。

我们已经给出

• 一个字符串 X。
• 我们通过多次重复 X 来形成一个字符串 S。
• 有 Q 个查询，每个查询包含两个索引 i 和 j。
• 对于每个查询，你需要确定无限重复的字符串 S 中索引 i 和 j 处的字符是否相同。如果相同，则打印“Yes”，否则打印“No”。

示例

• 字符串 X = "abc"。
• 如果我们考虑 S 是无限重复的：“abcabcabcabc...”。
• 假设有两个查询
• 查询 1：i = 2 且 j = 5。
• 查询 2：i = 3 且 j = 9。

对于查询 1

• 重复字符串中索引 2 处的字符是 'c'。
• 重复字符串中索引 5 处的字符是 'b'。
• 由于它们不相同，此查询的输出是“No”。

对于查询 2

• 重复字符串中索引 3 处的字符是 'a'。
• 重复字符串中索引 9 处的字符也是 'a'。
• 由于它们相同，此查询的输出是“Yes”。

方法

1. 确定重复字符串中的字符位置
   
   • 由于字符串 S 是 X 的无限重复，你可以使用模运算找到任何索引 k 处的字符
   • S 中索引 k 处的字符等价于 X 中索引 (k % X.length()) 处的字符。
2. 处理每个查询
   
   • 对于每个查询，计算 (i % X.length()) 和 (j % X.length()) 以找到它们在字符串 X 中对应的字符。
   • 比较字符；如果它们匹配，则打印“Yes”，否则打印“No”。

实施

文件名：RepeatedStringQuery.java

输入

输出

 
No
Yes
Yes   

代码解释

1. processQueries() 方法
   
   • 此方法接受字符串 X 和查询的二维数组作为输入。
   • 它使用模运算来获取索引 i 和 j 处的字符。
   • 它比较字符，如果它们相同则打印“Yes”；否则打印“No”。
2. main() 方法
   
   • 该方法从用户处读取字符串 X 和查询数 Q。
   • 然后它读取每个查询并将它们存储在二维数组中。
   • 调用 processQueries 方法来处理和打印所有查询的结果。

示例演练

让我们通过示例来分析

1. 输入
   
   • X = "abc"
   • 查询数，Q = 2
   • 查询
   • 查询 1：i = 2, j = 5
   • 查询 2：i = 3, j = 9
2. 处理查询 1 (i = 2, j = 5)
   
   • charAtI = X.charAt(2 % 3) = X.charAt(2) = 'c'
   • charAtJ = X.charAt(5 % 3) = X.charAt(2) = 'b'
   • 'c' 不等于 'b'，因此输出是“No”。
3. 处理查询 2 (i = 3, j = 9)
   
   • charAtI = X.charAt(3 % 3) = X.charAt(0) = 'a'
   • charAtJ = X.charAt(9 % 3) = X.charAt(0) = 'a'
   • 'a' 等于 'a'，因此输出是“Yes”。

复杂度分析

时间复杂度

处理每个查询的时间复杂度为 O(1)，因为模运算和字符比较是恒定时间操作。因此，对于 Q 个查询，总时间复杂度为 O(Q)。

空间复杂度

空间复杂度对于处理逻辑是 O(1)，不包括存储输入查询的空间 (O(Q))。

结论

该解决方案通过利用模运算在无限字符串重复中的性质来有效地处理问题。它确保了每个查询的快速处理，使其适用于大量输入。