snipt

Ctrl+h for KB shortcuts

C++

shortest substring contains all characters of another string

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;


/*
* given a string s1 and another string s2, find the shortest substring from s1 so that the 
* substring contains all characters of s2
* the key idea is to grow a substring window until it contains all characters of s2 and then shrink the lower end of the 
* window until it fails to meet the condition.
* 
*/
string shortestSubstr(const string& s1, const string& s2) {
  vector<int> hist1(26,0);
  vector<int> hist2(26,0);
  int uniqCnt = 0;
  
  for (auto c: s2) {
    if (!hist2[c - 'a']) uniqCnt++;
    hist2[c - 'a']++;
  }
  
  int minLen = s1.size() + 1;
  string minStr;
  
  int numExist = 0;
  
  size_t i = 0, j = 0;
  
  for (; i < s1.size(); i++) {
    char c = s1[i];
    int cidx = c - 'a';
    if (hist2[cidx]) {
      hist1[cidx]++;
      if (hist1[cidx] == hist2[cidx]) {
        numExist++;
      }
    }
    if (numExist == uniqCnt) {
      int curLen = i - j + 1;
      if (curLen < minLen) {
        minLen = curLen;
        minStr = s1.substr(j,curLen);
      }
      for (; j < i; j++) {
        char c = s1[j];
        int cidx = c - 'a';
        if(hist2[cidx]) {
          hist1[cidx]--;
          if (hist1[cidx] < hist2[cidx]) {
            int curLen = i - j + 1;
            if (curLen < minLen) {
              minLen = curLen;
              minStr = s1.substr(j,i - j + 1);
            }
            numExist--;
            j++;
            break;
          }
        }
      }
    }
  }
  
  return minStr;
}

int main() {
  string s1 = "ababaaacba";
  string s2 = "abc";
  string result = shortestSubstr(s1,s2);
  cout << "shortest substring for " << s1 << " is:" << result << endl;
  return 0;
}
https://snipt.net/embed/4e58dc4159e1dc5134ae663165c5b144/
/raw/4e58dc4159e1dc5134ae663165c5b144/
4e58dc4159e1dc5134ae663165c5b144
cpp
C++
78
2019-08-18T21:51:15
True
False
False
/api/public/snipt/142279/
shortest-substring-contains-all-characters-of-another-string
<table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><a href="#L-1"> 1</a> <a href="#L-2"> 2</a> <a href="#L-3"> 3</a> <a href="#L-4"> 4</a> <a href="#L-5"> 5</a> <a href="#L-6"> 6</a> <a href="#L-7"> 7</a> <a href="#L-8"> 8</a> <a href="#L-9"> 9</a> <a href="#L-10">10</a> <a href="#L-11">11</a> <a href="#L-12">12</a> <a href="#L-13">13</a> <a href="#L-14">14</a> <a href="#L-15">15</a> <a href="#L-16">16</a> <a href="#L-17">17</a> <a href="#L-18">18</a> <a href="#L-19">19</a> <a href="#L-20">20</a> <a href="#L-21">21</a> <a href="#L-22">22</a> <a href="#L-23">23</a> <a href="#L-24">24</a> <a href="#L-25">25</a> <a href="#L-26">26</a> <a href="#L-27">27</a> <a href="#L-28">28</a> <a href="#L-29">29</a> <a href="#L-30">30</a> <a href="#L-31">31</a> <a href="#L-32">32</a> <a href="#L-33">33</a> <a href="#L-34">34</a> <a href="#L-35">35</a> <a href="#L-36">36</a> <a href="#L-37">37</a> <a href="#L-38">38</a> <a href="#L-39">39</a> <a href="#L-40">40</a> <a href="#L-41">41</a> <a href="#L-42">42</a> <a href="#L-43">43</a> <a href="#L-44">44</a> <a href="#L-45">45</a> <a href="#L-46">46</a> <a href="#L-47">47</a> <a href="#L-48">48</a> <a href="#L-49">49</a> <a href="#L-50">50</a> <a href="#L-51">51</a> <a href="#L-52">52</a> <a href="#L-53">53</a> <a href="#L-54">54</a> <a href="#L-55">55</a> <a href="#L-56">56</a> <a href="#L-57">57</a> <a href="#L-58">58</a> <a href="#L-59">59</a> <a href="#L-60">60</a> <a href="#L-61">61</a> <a href="#L-62">62</a> <a href="#L-63">63</a> <a href="#L-64">64</a> <a href="#L-65">65</a> <a href="#L-66">66</a> <a href="#L-67">67</a> <a href="#L-68">68</a> <a href="#L-69">69</a> <a href="#L-70">70</a> <a href="#L-71">71</a> <a href="#L-72">72</a> <a href="#L-73">73</a> <a href="#L-74">74</a> <a href="#L-75">75</a> <a href="#L-76">76</a> <a href="#L-77">77</a></pre></div></td><td class="code"><div class="highlight"><pre><span></span><span id="L-1"><a name="L-1"></a><span class="cp">#include</span> <span class="cpf">&lt;iostream&gt;</span><span class="cp"></span> </span><span id="L-2"><a name="L-2"></a><span class="cp">#include</span> <span class="cpf">&lt;vector&gt;</span><span class="cp"></span> </span><span id="L-3"><a name="L-3"></a><span class="cp">#include</span> <span class="cpf">&lt;algorithm&gt;</span><span class="cp"></span> </span><span id="L-4"><a name="L-4"></a><span class="cp">#include</span> <span class="cpf">&lt;stack&gt;</span><span class="cp"></span> </span><span id="L-5"><a name="L-5"></a> </span><span id="L-6"><a name="L-6"></a><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> </span><span id="L-7"><a name="L-7"></a> </span><span id="L-8"><a name="L-8"></a> </span><span id="L-9"><a name="L-9"></a><span class="cm">/*</span> </span><span id="L-10"><a name="L-10"></a><span class="cm">* given a string s1 and another string s2, find the shortest substring from s1 so that the </span> </span><span id="L-11"><a name="L-11"></a><span class="cm">* substring contains all characters of s2</span> </span><span id="L-12"><a name="L-12"></a><span class="cm">* the key idea is to grow a substring window until it contains all characters of s2 and then shrink the lower end of the </span> </span><span id="L-13"><a name="L-13"></a><span class="cm">* window until it fails to meet the condition.</span> </span><span id="L-14"><a name="L-14"></a><span class="cm">* </span> </span><span id="L-15"><a name="L-15"></a><span class="cm">*/</span> </span><span id="L-16"><a name="L-16"></a><span class="n">string</span> <span class="nf">shortestSubstr</span><span class="p">(</span><span class="k">const</span> <span class="n">string</span><span class="o">&amp;</span> <span class="n">s1</span><span class="p">,</span> <span class="k">const</span> <span class="n">string</span><span class="o">&amp;</span> <span class="n">s2</span><span class="p">)</span> <span class="p">{</span> </span><span id="L-17"><a name="L-17"></a> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">hist1</span><span class="p">(</span><span class="mi">26</span><span class="p">,</span><span class="mi">0</span><span class="p">);</span> </span><span id="L-18"><a name="L-18"></a> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">hist2</span><span class="p">(</span><span class="mi">26</span><span class="p">,</span><span class="mi">0</span><span class="p">);</span> </span><span id="L-19"><a name="L-19"></a> <span class="kt">int</span> <span class="n">uniqCnt</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> </span><span id="L-20"><a name="L-20"></a> </span><span id="L-21"><a name="L-21"></a> <span class="k">for</span> <span class="p">(</span><span class="k">auto</span> <span class="nl">c</span><span class="p">:</span> <span class="n">s2</span><span class="p">)</span> <span class="p">{</span> </span><span id="L-22"><a name="L-22"></a> <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">hist2</span><span class="p">[</span><span class="n">c</span> <span class="o">-</span> <span class="sc">&#39;a&#39;</span><span class="p">])</span> <span class="n">uniqCnt</span><span class="o">++</span><span class="p">;</span> </span><span id="L-23"><a name="L-23"></a> <span class="n">hist2</span><span class="p">[</span><span class="n">c</span> <span class="o">-</span> <span class="sc">&#39;a&#39;</span><span class="p">]</span><span class="o">++</span><span class="p">;</span> </span><span id="L-24"><a name="L-24"></a> <span class="p">}</span> </span><span id="L-25"><a name="L-25"></a> </span><span id="L-26"><a name="L-26"></a> <span class="kt">int</span> <span class="n">minLen</span> <span class="o">=</span> <span class="n">s1</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> </span><span id="L-27"><a name="L-27"></a> <span class="n">string</span> <span class="n">minStr</span><span class="p">;</span> </span><span id="L-28"><a name="L-28"></a> </span><span id="L-29"><a name="L-29"></a> <span class="kt">int</span> <span class="n">numExist</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> </span><span id="L-30"><a name="L-30"></a> </span><span id="L-31"><a name="L-31"></a> <span class="kt">size_t</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> </span><span id="L-32"><a name="L-32"></a> </span><span id="L-33"><a name="L-33"></a> <span class="k">for</span> <span class="p">(;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">s1</span><span class="p">.</span><span class="n">size</span><span class="p">();</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> </span><span id="L-34"><a name="L-34"></a> <span class="kt">char</span> <span class="n">c</span> <span class="o">=</span> <span class="n">s1</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> </span><span id="L-35"><a name="L-35"></a> <span class="kt">int</span> <span class="n">cidx</span> <span class="o">=</span> <span class="n">c</span> <span class="o">-</span> <span class="sc">&#39;a&#39;</span><span class="p">;</span> </span><span id="L-36"><a name="L-36"></a> <span class="k">if</span> <span class="p">(</span><span class="n">hist2</span><span class="p">[</span><span class="n">cidx</span><span class="p">])</span> <span class="p">{</span> </span><span id="L-37"><a name="L-37"></a> <span class="n">hist1</span><span class="p">[</span><span class="n">cidx</span><span class="p">]</span><span class="o">++</span><span class="p">;</span> </span><span id="L-38"><a name="L-38"></a> <span class="k">if</span> <span class="p">(</span><span class="n">hist1</span><span class="p">[</span><span class="n">cidx</span><span class="p">]</span> <span class="o">==</span> <span class="n">hist2</span><span class="p">[</span><span class="n">cidx</span><span class="p">])</span> <span class="p">{</span> </span><span id="L-39"><a name="L-39"></a> <span class="n">numExist</span><span class="o">++</span><span class="p">;</span> </span><span id="L-40"><a name="L-40"></a> <span class="p">}</span> </span><span id="L-41"><a name="L-41"></a> <span class="p">}</span> </span><span id="L-42"><a name="L-42"></a> <span class="k">if</span> <span class="p">(</span><span class="n">numExist</span> <span class="o">==</span> <span class="n">uniqCnt</span><span class="p">)</span> <span class="p">{</span> </span><span id="L-43"><a name="L-43"></a> <span class="kt">int</span> <span class="n">curLen</span> <span class="o">=</span> <span class="n">i</span> <span class="o">-</span> <span class="n">j</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> </span><span id="L-44"><a name="L-44"></a> <span class="k">if</span> <span class="p">(</span><span class="n">curLen</span> <span class="o">&lt;</span> <span class="n">minLen</span><span class="p">)</span> <span class="p">{</span> </span><span id="L-45"><a name="L-45"></a> <span class="n">minLen</span> <span class="o">=</span> <span class="n">curLen</span><span class="p">;</span> </span><span id="L-46"><a name="L-46"></a> <span class="n">minStr</span> <span class="o">=</span> <span class="n">s1</span><span class="p">.</span><span class="n">substr</span><span class="p">(</span><span class="n">j</span><span class="p">,</span><span class="n">curLen</span><span class="p">);</span> </span><span id="L-47"><a name="L-47"></a> <span class="p">}</span> </span><span id="L-48"><a name="L-48"></a> <span class="k">for</span> <span class="p">(;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">i</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> </span><span id="L-49"><a name="L-49"></a> <span class="kt">char</span> <span class="n">c</span> <span class="o">=</span> <span class="n">s1</span><span class="p">[</span><span class="n">j</span><span class="p">];</span> </span><span id="L-50"><a name="L-50"></a> <span class="kt">int</span> <span class="n">cidx</span> <span class="o">=</span> <span class="n">c</span> <span class="o">-</span> <span class="sc">&#39;a&#39;</span><span class="p">;</span> </span><span id="L-51"><a name="L-51"></a> <span class="k">if</span><span class="p">(</span><span class="n">hist2</span><span class="p">[</span><span class="n">cidx</span><span class="p">])</span> <span class="p">{</span> </span><span id="L-52"><a name="L-52"></a> <span class="n">hist1</span><span class="p">[</span><span class="n">cidx</span><span class="p">]</span><span class="o">--</span><span class="p">;</span> </span><span id="L-53"><a name="L-53"></a> <span class="k">if</span> <span class="p">(</span><span class="n">hist1</span><span class="p">[</span><span class="n">cidx</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">hist2</span><span class="p">[</span><span class="n">cidx</span><span class="p">])</span> <span class="p">{</span> </span><span id="L-54"><a name="L-54"></a> <span class="kt">int</span> <span class="n">curLen</span> <span class="o">=</span> <span class="n">i</span> <span class="o">-</span> <span class="n">j</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> </span><span id="L-55"><a name="L-55"></a> <span class="k">if</span> <span class="p">(</span><span class="n">curLen</span> <span class="o">&lt;</span> <span class="n">minLen</span><span class="p">)</span> <span class="p">{</span> </span><span id="L-56"><a name="L-56"></a> <span class="n">minLen</span> <span class="o">=</span> <span class="n">curLen</span><span class="p">;</span> </span><span id="L-57"><a name="L-57"></a> <span class="n">minStr</span> <span class="o">=</span> <span class="n">s1</span><span class="p">.</span><span class="n">substr</span><span class="p">(</span><span class="n">j</span><span class="p">,</span><span class="n">i</span> <span class="o">-</span> <span class="n">j</span> <span class="o">+</span> <span class="mi">1</span><span class="p">);</span> </span><span id="L-58"><a name="L-58"></a> <span class="p">}</span> </span><span id="L-59"><a name="L-59"></a> <span class="n">numExist</span><span class="o">--</span><span class="p">;</span> </span><span id="L-60"><a name="L-60"></a> <span class="n">j</span><span class="o">++</span><span class="p">;</span> </span><span id="L-61"><a name="L-61"></a> <span class="k">break</span><span class="p">;</span> </span><span id="L-62"><a name="L-62"></a> <span class="p">}</span> </span><span id="L-63"><a name="L-63"></a> <span class="p">}</span> </span><span id="L-64"><a name="L-64"></a> <span class="p">}</span> </span><span id="L-65"><a name="L-65"></a> <span class="p">}</span> </span><span id="L-66"><a name="L-66"></a> <span class="p">}</span> </span><span id="L-67"><a name="L-67"></a> </span><span id="L-68"><a name="L-68"></a> <span class="k">return</span> <span class="n">minStr</span><span class="p">;</span> </span><span id="L-69"><a name="L-69"></a><span class="p">}</span> </span><span id="L-70"><a name="L-70"></a> </span><span id="L-71"><a name="L-71"></a><span class="kt">int</span> <span class="nf">main</span><span class="p">()</span> <span class="p">{</span> </span><span id="L-72"><a name="L-72"></a> <span class="n">string</span> <span class="n">s1</span> <span class="o">=</span> <span class="s">&quot;ababaaacba&quot;</span><span class="p">;</span> </span><span id="L-73"><a name="L-73"></a> <span class="n">string</span> <span class="n">s2</span> <span class="o">=</span> <span class="s">&quot;abc&quot;</span><span class="p">;</span> </span><span id="L-74"><a name="L-74"></a> <span class="n">string</span> <span class="n">result</span> <span class="o">=</span> <span class="n">shortestSubstr</span><span class="p">(</span><span class="n">s1</span><span class="p">,</span><span class="n">s2</span><span class="p">);</span> </span><span id="L-75"><a name="L-75"></a> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">&quot;shortest substring for &quot;</span> <span class="o">&lt;&lt;</span> <span class="n">s1</span> <span class="o">&lt;&lt;</span> <span class="s">&quot; is:&quot;</span> <span class="o">&lt;&lt;</span> <span class="n">result</span> <span class="o">&lt;&lt;</span> <span class="n">endl</span><span class="p">;</span> </span><span id="L-76"><a name="L-76"></a> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> </span><span id="L-77"><a name="L-77"></a><span class="p">}</span> </span></pre></div> </td></tr></table>
histogram, search, shortest, string
--- 
+++ 
@@ -5,6 +5,14 @@
 
 using namespace std;
 
+
+/*
+* given a string s1 and another string s2, find the shortest substring from s1 so that the 
+* substring contains all characters of s2
+* the key idea is to grow a substring window until it contains all characters of s2 and then shrink the lower end of the 
+* window until it fails to meet the condition.
+* 
+*/
 string shortestSubstr(const string& s1, const string& s2) {
   vector<int> hist1(26,0);
   vector<int> hist2(26,0);
--- 
+++ 
@@ -0,0 +1,69 @@
+#include <iostream>
+#include <vector>
+#include <algorithm>
+#include <stack>
+
+using namespace std;
+
+string shortestSubstr(const string& s1, const string& s2) {
+  vector<int> hist1(26,0);
+  vector<int> hist2(26,0);
+  int uniqCnt = 0;
+  
+  for (auto c: s2) {
+    if (!hist2[c - 'a']) uniqCnt++;
+    hist2[c - 'a']++;
+  }
+  
+  int minLen = s1.size() + 1;
+  string minStr;
+  
+  int numExist = 0;
+  
+  size_t i = 0, j = 0;
+  
+  for (; i < s1.size(); i++) {
+    char c = s1[i];
+    int cidx = c - 'a';
+    if (hist2[cidx]) {
+      hist1[cidx]++;
+      if (hist1[cidx] == hist2[cidx]) {
+        numExist++;
+      }
+    }
+    if (numExist == uniqCnt) {
+      int curLen = i - j + 1;
+      if (curLen < minLen) {
+        minLen = curLen;
+        minStr = s1.substr(j,curLen);
+      }
+      for (; j < i; j++) {
+        char c = s1[j];
+        int cidx = c - 'a';
+        if(hist2[cidx]) {
+          hist1[cidx]--;
+          if (hist1[cidx] < hist2[cidx]) {
+            int curLen = i - j + 1;
+            if (curLen < minLen) {
+              minLen = curLen;
+              minStr = s1.substr(j,i - j + 1);
+            }
+            numExist--;
+            j++;
+            break;
+          }
+        }
+      }
+    }
+  }
+  
+  return minStr;
+}
+
+int main() {
+  string s1 = "ababaaacba";
+  string s2 = "abc";
+  string result = shortestSubstr(s1,s2);
+  cout << "shortest substring for " << s1 << " is:" << result << endl;
+  return 0;
+}