title: Similar Char(TCS CodeVita) Reduce Time Complexity
body: <p>You have to take the length of the string from the user then input the string from the user, after that take the no. of queries from the user to check. Suppose that the user gives 3 queries 4,5,7. Then 4,5,7 are the position where you have to check how many of the same characters are repeated before that position.</p>
  
  <p>Inputs:</p>
  
  <ol>
  <li>9 (Length of the string to input)</li>
  <li>abcabcabc</li>
  <li>3 (No. of queries to check)</li>
  <li>4 (Check at position 4)</li>
  <li>5 (Check at position 5)</li>
  <li>7 (Check at position 7)</li>
  </ol>
  
  <p>Output:</p>
  
  <ol>
  <li>1</li>
  <li>1</li>
  <li>2    </li>
  </ol>
  
  <p><strong>Code which I made:</strong></p>
  
  <pre><code>#include &lt;iostream&gt;
  
  int main()
  {
      int n; // Length of String
      int a[10000]; // Input for Query
      int q; // NO. of queries
      std::cin &gt;&gt; n;
      char ch[n]; // To store the InputString
  
      for (int i = 1; i &lt;= n; i++) {
          std::cin &gt;&gt; ch[i];
      }
  
      std::cin &gt;&gt; q;
  
      for (int j = 1; j &lt;= q; j++) {
          std::cin &gt;&gt; a[j];
      }
  
      for (int i = 1; i &lt;= q; i++) {
          int count = 0;
          for (int j = 1; j &lt; a[i]; j++) {
              if (ch[j] == ch[a[i]]) {
                  count = count + 1;
              }
          }
          std::cout &lt;&lt; count &lt;&lt; "\n";
      }
      return 0;
  }
  </code></pre>
  
  <p>But the problem is this the time complexity of the program is too much.In worst case it would be <strong>O(n*q)</strong>, where n = length of the string and q = number of queries. How to improve the time complexity?</p>